An exponential lower bound on the size of static Lovász-Schrijver proofs of Tseitin tautologies is established. Several techniques, such as translating a static LS+ proof into a Positivstellensatz proof, extracting a "good" expander out of a given graph by removing edges and vertices, and proving a linear lower bound on the degree of Positivstellensatz proofs for Tseitin tautologies, are used. Bibliography: 22 titles.

Original languageEnglish
Pages (from-to)4942-4952
Number of pages11
JournalJournal of Mathematical Sciences
Volume145
Issue number3
DOIs
StatePublished - 1 Sep 2007

    Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Applied Mathematics

ID: 49786962