Feasibly constructive proofs of succinct weak circuit lower bounds
From MaRDI portal
Publication:2007873
DOI10.1016/j.apal.2019.102735zbMath1454.03078OpenAlexW2972703483WikidataQ113880326 ScholiaQ113880326MaRDI QIDQ2007873
Publication date: 22 November 2019
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2117/177667
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Approximate counting and NP search problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hardness magnification near state-of-the-art lower bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Circuit lower bounds in bounded arithmetics
- Almost-natural proofs
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- 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
- A model-theoretic characterization of the weak pigeonhole principle
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Structures interpretable in models of bounded arithmetic
- On the weak pigeonhole principle
- Simple strategies for large zero-sum games with applications to complexity theory
- FRAGMENTS OF APPROXIMATE COUNTING
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- The Ordering Principle in a Fragment of Approximate Counting
- Unprovability of circuit upper bounds in Cook's theory PV
- The Circuit-Input Game, Natural Proofs, and Testing Circuits With Data
- Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
- Parity, circuits, and the polynomial-time hierarchy
- Approximate counting by hashing in bounded arithmetic
- The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Hilbert's Twenty-Fourth Problem
- Pseudorandom Generators in Propositional Proof Complexity
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Hardness magnification near state-of-the-art lower bounds
- A remark on pseudo proof systems and hard instances of the satisfiability problem
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Computational Complexity
- Learning algorithms from natural proofs
- Approximate counting in bounded arithmetic
- On Independence of Variants of the Weak Pigeonhole Principle
- Consequences of the provability of NP ⊆ P/poly
- Resolution lower bounds for the weak pigeonhole principle
- Existence and feasibility in arithmetic
- A new proof of the weak pigeonhole principle
- Natural proofs
