Exponential lower bounds for AC^0-Frege imply superpolynomial Frege lower bounds

DOI10.1007/978-3-642-22006-7_52MaRDI QIDQ3012837zbMATH OpenOpenAlexFDO

Authors Yuval Filmus, Toniann Pitassi, Rahul Santhanam

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

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of proofs (03F20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Exponential lower bounds for \(\mathrm{AC}^0\)-Frege imply superpolynomial Frege lower bounds
• Non-automatizability of bounded-depth Frege proofs
• On Interpolation and Automatization for Frege Systems
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• Exponential lower bounds for the pigeonhole principle

Cites work

• scientific article; zbMATH DE number 806744 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• Lower bounds to the size of constant-depth propositional proofs
• Mean-payoff games and propositional proofs
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
• Non-automatizability of bounded-depth Frege proofs
• On Interpolation and Automatization for Frege Systems
• Polynomial size proofs of the propositional pigeonhole principle
• The intractability of resolution
• The relative efficiency of propositional proof systems

Cited in

(3)

• Non-automatizability of bounded-depth Frege proofs
• Feasibly constructive proofs of succinct weak circuit lower bounds
• Exponential lower bounds for \(\mathrm{AC}^0\)-Frege imply superpolynomial Frege lower bounds

This page was built for publication: Exponential lower bounds for \(\mathrm{AC}^{0}\)-Frege imply superpolynomial Frege lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3012837)