Lower bounds on static Lovász-Schrijver calculus proofs for Tseitin tautologies
Copyright policy )Lower bounds on static Lovász-Schrijver calculus proofs for Tseitin tautologies
Summary: We prove an exponential lower bound on the size of static Lovász-Schrijver proofs of Tseitin tautologies. We use several techniques, namely, translating a static LS\(_+\) proof into a Positivstellensatz proof as done by \textit{D. Grigoriev} and \textit{N. Vorobjov} [Ann. Pure Appl. Log. 113, 153--160 (2002; Zbl 0992.03073)], extracting a ``good'' expander out of a given graph by removing edges and vertices as done by \textit{M. Alekhnovich, E. A. Hirsch} and \textit{D. Itsykson} [J. Autom. Reasoning 35, 51--72 (2005; Zbl 1109.68098)], and proving linear lower bounds on the degree of Positivstellensatz proofs for Tseitin tautologies.
- St. Petersburg Department of Steklov Institute of Mathematics Russian Federation
- Steklov Mathematical Institute Russian Federation
- St Petersburg University Russian Federation
- Department of Mathematical Sciences Russian Federation
Complexity of proofs, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Complexity of proofs, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).36 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!