Unprovability of strong complexity lower bounds in bounded arithmetic
From MaRDI portal
Publication:6499282
DOI10.1145/3564246.3585144MaRDI QIDQ6499282
Igor C. Oliveira, Unnamed Author
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Circuit lower bounds in bounded arithmetics
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The monotone circuit complexity of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded arithmetic and the polynomial hierarchy
- Hardness vs randomness
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Relating the bounded arithmetic and polynomial time hierarchies
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Iterated multiplication in \(VTC^0\)
- Expander construction in \(\mathrm{VNC}^1\)
- Polynomial time ultrapowers and the consistency of circuit lower bounds
- Upper and lower Ramsey bounds in bounded arithmetic
- On the weak pigeonhole principle
- Formalizing Randomized Matching Algorithms
- FRAGMENTS OF APPROXIMATE COUNTING
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Algebrization
- Unprovability of circuit upper bounds in Cook's theory PV
- Nonuniform ACC Circuit Lower Bounds
- Parity, circuits, and the polynomial-time hierarchy
- Amplifying lower bounds by means of self-reducibility
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Proof Complexity
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Uniform, Integral, and Feasible Proofs for the Determinant Identities
- Approximate counting in bounded arithmetic
- Consequences of the provability of NP ⊆ P/poly
- Using Nondeterminism to Amplify Hardness
- Notes on polynomially bounded arithmetic
- Beyond Natural Proofs: Hardness Magnification and Locality
- Natural proofs
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
This page was built for publication: Unprovability of strong complexity lower bounds in bounded arithmetic
