Pages that link to "Item:Q4864743"
From MaRDI portal
The following pages link to Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic (Q4864743):
Displaying 32 items.
- Towards NP-P via proof complexity and search (Q408544) (← links)
- Circuit lower bounds in bounded arithmetics (Q466447) (← links)
- Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic (Q866557) (← links)
- \(S_{k,\text{exp}}\) does not prove \(\text{NP} = \text{co-NP}\) uniformly (Q937909) (← links)
- Resolution over linear equations and multilinear proofs (Q952492) (← links)
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF (Q1383164) (← links)
- A note on monotone real circuits (Q1685020) (← links)
- On the automatizability of resolution and related propositional proof systems (Q1881219) (← links)
- Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution (Q2255289) (← links)
- Polynomial time ultrapowers and the consistency of circuit lower bounds (Q2288334) (← links)
- Unifying known lower bounds via geometric complexity theory (Q2351393) (← links)
- Dag-like communication and its applications (Q2399382) (← links)
- $$P\mathop{ =}\limits^{?}NP$$ (Q2826803) (← links)
- Unprovability of circuit upper bounds in Cook's theory PV (Q2980966) (← links)
- A feasible interpolation for random resolution (Q2980967) (← links)
- A form of feasible interpolation for constant depth Frege systems (Q3570172) (← links)
- On the correspondence between arithmetic theories and propositional proof systems – a survey (Q3619867) (← links)
- Some applications of propositional logic to cellular automata (Q3650319) (← links)
- Polynomially and superexponentially shorter proofs in fragments of arithmetic (Q4032866) (← links)
- Randomized feasible interpolation and monotone circuits with a local oracle (Q4562441) (← links)
- Reflections on Proof Complexity and Counting Principles (Q5027248) (← links)
- Hardness magnification near state-of-the-art lower bounds (Q5028364) (← links)
- Adventures in monotone complexity and TFNP (Q5090415) (← links)
- Hardness magnification near state-of-the-art lower bounds (Q5091779) (← links)
- Monotone circuit lower bounds from resolution (Q5140848) (← links)
- NP search problems in low fragments of bounded arithmetic (Q5294030) (← links)
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes (Q5889793) (← links)
- A new proof of the weak pigeonhole principle (Q5894824) (← links)
- Natural proofs (Q5906823) (← links)
- Complexity barriers as independence (Q6599290) (← links)
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 (Q6613418) (← links)
