Unprovability of strong complexity lower bounds in bounded arithmetic
From MaRDI portal
Publication:6499282
DOI10.1145/3564246.3585144MaRDI QIDQ6499282FDOQ6499282
Authors: Igor C. Oliveira 
Publication date: 8 May 2024
Cites Work
- Title not available (Why is that?)
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Hardness vs randomness
- Notes on polynomially bounded arithmetic
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Logical foundations of proof complexity
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Parity, circuits, and the polynomial-time hierarchy
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Natural proofs
- Algebrization
- Amplifying lower bounds by means of self-reducibility
- On the weak pigeonhole principle
- Title not available (Why is that?)
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Consequences of the provability of NP ⊆ P/poly
- Using Nondeterminism to Amplify Hardness
- Bounded arithmetic and the polynomial hierarchy
- Title not available (Why is that?)
- Circuit lower bounds in bounded arithmetics
- Approximate counting in bounded arithmetic
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Title not available (Why is that?)
- Relating the bounded arithmetic and polynomial time hierarchies
- Title not available (Why is that?)
- Nonuniform ACC Circuit Lower Bounds
- Fragments of approximate counting
- On the correspondence between arithmetic theories and propositional proof systems – a survey
- Proof Complexity
- Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
- Formalizing randomized matching algorithms
- Uniform, Integral, and Feasible Proofs for the Determinant Identities
- Beyond Natural Proofs: Hardness Magnification and Locality
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Unprovability of circuit upper bounds in Cook's theory PV
- 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
- Title not available (Why is that?)
This page was built for publication: Unprovability of strong complexity lower bounds in bounded arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499282)
