Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANASTASIA SOFRONOVA:
All reports by Author Anastasia Sofronova:

TR19-069 | 6th May 2019
Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

Bounded-depth Frege complexity of Tseitin formulas for all graphs

Revisions: 1

We prove that there is a constant $K$ such that \emph{Tseitin} formulas for an undirected graph $G$ requires proofs of
size $2^{\mathrm{tw}(G)^{\Omega(1/d)}}$ in depth-$d$ Frege systems for $d<\frac{K \log n}{\log \log n}$, where $\tw(G)$ is the treewidth of $G$. This extends H{\aa}stad recent lower bound for the grid graph ... more >>>




ISSN 1433-8092 | Imprint