Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies | Zendy

Arist Kojevnikov | Zendy; Dmitry Itsykson | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies

Author(s) -

Arist Kojevnikov,

Dmitry Itsykson

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/11786986_29

Subject(s) - mathematical proof , upper and lower bounds , discrete mathematics , proof complexity , calculus (dental) , graph , exponential function , computer science , mathematics , combinatorics , geometry , medicine , mathematical analysis , dentistry

We prove an exponential lower bound on the size of static Lovasz- Schrijver proofs of Tseitin tautologies. We use several techniques, namely, translating static LS+ proof into 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research