Bounded-depth Frege complexity of Tseitin formulas for all graphs.

Nicola Galesi Dmitry Itsykson Artur Riazanov Anastasia Sofronova

Published in: Ann. Pure Appl. Log. (2023)

Keyphrases

semidefinite
worst case
semidefinite programming
bounded treewidth
lower bound