Lower bounds of static Lovász–Schrijver calculus proofs for Tseitin tautologies

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.