BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs Galesi, Nicola


We prove that Tseitin formulas $Ts(G)$ for an undirected graph $G$, requires proofs of size $2^{tw(G)^{\Omega(1/d)}}$ in depth d-Frege systems for $d<{K \log n}/{\log \log n}$, where $tw(G)$ is the treewidth of $G$ and $K$ a constant. This extends H\r{a}stad recent lower bound for the grid graph to any graph. Furthermore, we prove tightness of our bound up to a multiplicative constant in the top exponent. The talk is based on a joint work with Dmitry Itsykson, Artur Ryazonov, Anastasia Sofronova.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International