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

Description

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

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International