Geodesic
Lower bounds of static Lov\'asz--Schrijver calculus proofs for Tseitin tautologies
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part I, Tome 340 (2006), pp. 10-32

Voir la notice de l'article provenant de la source Math-Net.Ru

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 of Grigoriev et al., extracting a “good” expander out of a given graph by removing edges and vertices of Alekhnovich et al., and proving linear lower bound on the degree of Positivstellensatz proofs for Tseitin tautologies. 
@article{ZNSL_2006_340_a1,
     author = {D. M. Itsykson and A. A. Kojevnikov},
     title = {Lower bounds of static {Lov\'asz--Schrijver} calculus proofs for {Tseitin} tautologies},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {10--32},
     publisher = {mathdoc},
     volume = {340},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a1/}
}
TY  - JOUR
AU  - D. M. Itsykson
AU  - A. A. Kojevnikov
TI  - Lower bounds of static Lov\'asz--Schrijver calculus proofs for Tseitin tautologies
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2006
SP  - 10
EP  - 32
VL  - 340
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a1/
LA  - ru
ID  - ZNSL_2006_340_a1
ER  - 
%0 Journal Article
%A D. M. Itsykson
%A A. A. Kojevnikov
%T Lower bounds of static Lov\'asz--Schrijver calculus proofs for Tseitin tautologies
%J Zapiski Nauchnykh Seminarov POMI
%D 2006
%P 10-32
%V 340
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a1/
%G ru
%F ZNSL_2006_340_a1
D. M. Itsykson; A. A. Kojevnikov. Lower bounds of static Lov\'asz--Schrijver calculus proofs for Tseitin tautologies. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part I, Tome 340 (2006), pp. 10-32. http://geodesic.mathdoc.fr/item/ZNSL_2006_340_a1/