Skip to main content

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

Publication ,  Conference
Pitassi, T; Rossman, B; Tan, LY; Servedio, RA
Published in: Proceedings of the Annual ACM Symposium on Theory of Computing
June 19, 2016

We show that any polynomial-size Frege refutation of a certain linear-size unsatisfiable 3-CNF formula over n variables must have depth Ω(√logn). This is an exponential improvement over the previous best results (Pitassi et al. 1993, Krajíček et al. 1995, Ben-Sasson 2002) which give Ω(log log n) lower bounds. The 3-CNF formulas which we use to establish this result are Tseitin contradictions on 3-regular expander graphs. In more detail, our main result is a proof that for every d, any depth-d Frege refutation of the Tseitin contradiction over these n-node graphs must have size nΩ(logn n)/d2). A key ingredient of our approach is a new switching lemma for a carefully designed random restriction process over these expanders. These random restrictions reduce a Tseitin instance on a 3-regular n-node expander to a Tseitin instance on a random subgraph which is a topological embedding of a 3-regular n'-node expander, for some n' which is not too much less than n. Our result involves Ω(√logn) iterative applications of this type of random restriction.

Duke Scholars

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

Publication Date

June 19, 2016

Volume

19-21-June-2016

Start / End Page

644 / 657
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Pitassi, T., Rossman, B., Tan, L. Y., & Servedio, R. A. (2016). Poly-logarithmic Frege depth lower bounds via an expander switching lemma. In Proceedings of the Annual ACM Symposium on Theory of Computing (Vol. 19-21-June-2016, pp. 644–657). https://doi.org/10.1145/2897518.2897637
Pitassi, T., B. Rossman, L. Y. Tan, and R. A. Servedio. “Poly-logarithmic Frege depth lower bounds via an expander switching lemma.” In Proceedings of the Annual ACM Symposium on Theory of Computing, 19-21-June-2016:644–57, 2016. https://doi.org/10.1145/2897518.2897637.
Pitassi T, Rossman B, Tan LY, Servedio RA. Poly-logarithmic Frege depth lower bounds via an expander switching lemma. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2016. p. 644–57.
Pitassi, T., et al. “Poly-logarithmic Frege depth lower bounds via an expander switching lemma.” Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 19-21-June-2016, 2016, pp. 644–57. Scopus, doi:10.1145/2897518.2897637.
Pitassi T, Rossman B, Tan LY, Servedio RA. Poly-logarithmic Frege depth lower bounds via an expander switching lemma. Proceedings of the Annual ACM Symposium on Theory of Computing. 2016. p. 644–657.

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

Publication Date

June 19, 2016

Volume

19-21-June-2016

Start / End Page

644 / 657