From proof complexity to circuit complexity via interactive protocols
From MaRDI portal
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Algebraic methods for interactive proof systems
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Approximate counting in bounded arithmetic
- Approximation and Small-Depth Frege Proofs
- Bounded arithmetic and the polynomial hierarchy
- Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system
- Colourful TFNP and propositional proofs
- Completeness and reduction in algebraic complexity theory
- Computational Complexity
- Consequences of the provability of NP ⊆ P/poly
- Consistency of circuit evaluation, extended resolution and total NP search problems
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Diagonalization in proof complexity
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Every Prime Has a Succinct Certificate
- Exponential lower bounds for the pigeonhole principle
- Exponentiation and second-order bounded arithmetic
- Feasible interpolation for polynomial calculus and sums-of-squares
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Frege systems for quantified Boolean logic
- Hardness vs randomness
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 1114018 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 806753 (Why is no real title available?)
- scientific article; zbMATH DE number 7829336 (Why is no real title available?)
- Implicit proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lifting with simple gadgets and applications to circuit and proof complexity
- Logical foundations of proof complexity
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Lower bounds to the size of constant-depth propositional proofs
- Monotone circuit lower bounds from resolution
- Non-automatizability of bounded-depth Frege proofs
- On Interpolation and Automatization for Frege Systems
- Parity, circuits, and the polynomial-time hierarchy
- Proof Complexity
- Quantified propositional calculi and fragments of bounded arithmetic
- Quantum automating TC^0-Frege is LWE-hard
- Relating the bounded arithmetic and polynomial time hierarchies
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- The complexity of the pigeonhole principle
- The monotone circuit complexity of Boolean functions
- The NP search problems of Frege and extended Frege proofs
- The provably total NP search problems of weak second order bounded arithmetic
- The relative efficiency of propositional proof systems
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
This page was built for publication: From proof complexity to circuit complexity via interactive protocols
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875199)
