|
Zapiski Nauchnykh Seminarov POMI, 2006, Volume 340, Pages 10–32
(Mi znsl148)
|
|
|
|
This article is cited in 6 scientific papers (total in 6 papers)
Lower bounds of static Lovász–Schrijver calculus proofs for Tseitin tautologies
D. M. Itsyksona, A. A. Kojevnikovb a Saint-Petersburg State University
b St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
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.
Received: 28.07.2006
Citation:
D. M. Itsykson, A. A. Kojevnikov, “Lower bounds of static Lovász–Schrijver calculus proofs for Tseitin tautologies”, Combinatorics and graph theory. Part I, Zap. Nauchn. Sem. POMI, 340, POMI, St. Petersburg, 2006, 10–32; J. Math. Sci. (N. Y.), 145:3 (2007), 4942–4952
Linking options:
https://www.mathnet.ru/eng/znsl148 https://www.mathnet.ru/eng/znsl/v340/p10
|
Statistics & downloads: |
Abstract page: | 237 | Full-text PDF : | 86 | References: | 39 |
|