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

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

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 >>>