Poly-logarithmic Frege depth lower bounds via an expander switching lemma

DOI10.1145/2897518.2897637zbMath1373.03125OpenAlexW2417894922MaRDI QIDQ5361868

Li-Yang Tan, Benjamin Rossman, Toniann Pitassi, Rocco A. Servedio

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

random projectionssmall-depth circuitspropositional proof complexityFrege proof systemswitching lemma

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items

Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs ⋮ Unnamed Item ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Propositional proof complexity ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Reflections on Proof Complexity and Counting Principles