Math @ Duke

Publications [#348679] of Benjamin Rossman
Papers Published
 Pitassi, T; Rossman, B; Tan, LY; Servedio, RA, Polylogarithmic Frege depth lower bounds via an expander switching lemma,
Proceedings of the Annual Acm Symposium on Theory of Computing, vol. 1921June2016
(June, 2016),
pp. 644657, ISBN 9781450341325 [doi]
(last updated on 2022/05/21)
Abstract: We show that any polynomialsize Frege refutation of a certain linearsize unsatisfiable 3CNF 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, BenSasson 2002) which give Ω(log log n) lower bounds. The 3CNF formulas which we use to establish this result are Tseitin contradictions on 3regular expander graphs. In more detail, our main result is a proof that for every d, any depthd Frege refutation of the Tseitin contradiction over these nnode 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 3regular nnode expander to a Tseitin instance on a random subgraph which is a topological embedding of a 3regular 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

