Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies

DOI10.1007/11786986_29zbMath1223.03043OpenAlexW1680398520MaRDI QIDQ3613770

Dmitry Itsykson, Arist Kojevnikov

Publication date: 12 March 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11786986_29

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items

Tight size-degree bounds for sums-of-squares proofs, Nullstellensatz size-degree trade-offs from reversible pebbling, Nullstellensatz size-degree trade-offs from reversible pebbling