Exponential Lower Bounds for AC 0 -Frege Imply Superpolynomial Frege Lower Bounds

DOI10.1145/2656209zbMath1347.03101OpenAlexW1650544138MaRDI QIDQ2828228

Yuval Filmus, Toniann Pitassi, Rahul Santhanam

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2656209

zbMATH Keywords

proof complexity

Mathematics Subject Classification ID

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

This page was built for publication: Exponential Lower Bounds for AC ⁰ -Frege Imply Superpolynomial Frege Lower Bounds