Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
From MaRDI portal
Publication:3012837
DOI10.1007/978-3-642-22006-7_52zbMath1280.03055OpenAlexW2279614198MaRDI QIDQ3012837
Rahul Santhanam, Yuval Filmus, Toniann Pitassi
Publication date: 6 July 2011
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_52
Mechanization of proofs and logical operations (03B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Mean-payoff games and propositional proofs
- The intractability of resolution
- Non-automatizability of bounded-depth Frege proofs
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- Polynomial size proofs of the propositional pigeonhole principle
- The relative efficiency of propositional proof systems
- Lower bounds to the size of constant-depth propositional proofs
- On Interpolation and Automatization for Frege Systems