Unprovability of strong complexity lower bounds in bounded arithmetic

Cites work

scientific article; zbMATH DE number 4008289 (Why is no real title available?)
scientific article; zbMATH DE number 65757 (Why is no real title available?)
scientific article; zbMATH DE number 3557241 (Why is no real title available?)
scientific article; zbMATH DE number 3999837 (Why is no real title available?)
scientific article; zbMATH DE number 806753 (Why is no real title available?)
scientific article; zbMATH DE number 819737 (Why is no real title available?)
scientific article; zbMATH DE number 7215291 (Why is no real title available?)
scientific article; zbMATH DE number 5038466 (Why is no real title available?)
Algebrization: a new barrier in complexity theory
Amplifying lower bounds by means of self-reducibility
Approximate counting in bounded arithmetic
Beyond Natural Proofs: Hardness Magnification and Locality
Bounded arithmetic and the polynomial hierarchy
Circuit lower bounds in bounded arithmetics
Consequences of the provability of NP ⊆ P/poly
Expander construction in $\mathrm{VNC}^1$
Feasibly constructive proofs of succinct weak circuit lower bounds
Formalizing randomized matching algorithms
Fragments of approximate counting
Hardness vs randomness
Iterated multiplication in $VTC^0$
Logical foundations of proof complexity
Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
Natural proofs
Nonuniform ACC circuit lower bounds
Notes on polynomially bounded arithmetic
On the correspondence between arithmetic theories and propositional proof systems – a survey
On the weak pigeonhole principle
Parity, circuits, and the polynomial-time hierarchy
Polynomial time ultrapowers and the consistency of circuit lower bounds
Proof Complexity
Relating the bounded arithmetic and polynomial time hierarchies
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
Some consequences of cryptographical conjectures for $S_2^1$ and EF
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
The monotone circuit complexity of Boolean functions
Uniform, Integral, and Feasible Proofs for the Determinant Identities
Unprovability of circuit upper bounds in Cook's theory PV
Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Upper and lower Ramsey bounds in bounded arithmetic
Using Nondeterminism to Amplify Hardness
$\Sigma_ 1^ 1$-formulae on finite structures

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)