Research output: Contribution to journal › Article › peer-review
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 language | English |
|---|---|
| Pages (from-to) | 4942-4952 |
| Number of pages | 11 |
| Journal | Journal of Mathematical Sciences |
| Volume | 145 |
| Issue number | 3 |
| DOIs | |
| State | Published - 1 Sep 2007 |
ID: 49786962