{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T14:57:12Z","timestamp":1786978632955,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_29","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"323-334","source":"Crossref","is-referenced-by-count":10,"title":["Lower Bounds of Static Lov\u00e1sz-Schrijver Calculus Proofs for Tseitin Tautologies"],"prefix":"10.1007","author":[{"given":"Arist","family":"Kojevnikov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dmitry","family":"Itsykson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"29_CR1","first-page":"269","volume-title":"Recent Advances in Mathematical Programming","author":"R.E. Gomory","year":"1963","unstructured":"Gomory, R.E.: An algorithm for integer solutions of linear programs. In: Graves, R.L., Wolfe, P. (eds.) Recent Advances in Mathematical Programming, pp. 269\u2013302. McGraw-Hill, New York (1963)"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0012-365X(73)90167-2","volume":"4","author":"V. Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics\u00a04, 305\u2013337 (1973)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"29_CR3","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM J. Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM J. Optimization"},{"issue":"4","key":"29_CR4","doi-asserted-by":"crossref","first-page":"647","DOI":"10.17323\/1609-4514-2002-2-4-647-679","volume":"2","author":"D. Grigoriev","year":"2002","unstructured":"Grigoriev, D., Hirsch, E.A., Pasechnik, D.V.: Complexity of semialgebraic proofs. Moscow Mathematical Journal\u00a02(4), 647\u2013679 (2002)","journal-title":"Moscow Mathematical Journal"},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1176","DOI":"10.1007\/11523468_95","volume-title":"Automata, Languages and Programming","author":"P. Beame","year":"2005","unstructured":"Beame, P., Pitassi, T., Segerlind, N.: Lower Bounds for Lov\u00e1sz-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1176\u20131188. Springer, Heidelberg (2005)"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. Technical Report 04-041, ECCC (2004)","DOI":"10.1007\/978-3-540-27836-8_10"},{"key":"29_CR7","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1016\/S0304-3975(00)00157-2","volume":"259","author":"D. Grigoriev","year":"2001","unstructured":"Grigoriev, D.: Linear lower bound on degrees of Positivstellensatz Calculus proofs for the Parity. TCS\u00a0259, 613\u2013622 (2001)","journal-title":"TCS"},{"issue":"1","key":"29_CR8","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. The Journal of Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: STOC 1996, pp. 174\u2013183 (1996)","DOI":"10.1145\/237814.237860"},{"issue":"1-3","key":"29_CR10","first-page":"153","volume":"113","author":"D. Grigoriev","year":"2001","unstructured":"Grigoriev, D., Vorobjov, N.: Complexity of Null- and Positivstellensatz proofs. APAL\u00a0113(1-3), 153\u2013160 (2001)","journal-title":"APAL"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.: Lower bounds for polynomial calculus: Non-binomial case. In: FOCS 2001, pp. 190\u2013199 (1996)","DOI":"10.1109\/SFCS.2001.959893"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Kojevnikov, A., Itsykson, D.: Lower Bounds of Static Lov\u00e1sz-Schrijver Calculus Proofs for Tseitin Tautologies. Manuscript in preparation (2006)","DOI":"10.1007\/11786986_29"},{"issue":"1","key":"29_CR13","first-page":"1","volume":"18","author":"R. Murty","year":"2003","unstructured":"Murty, R.: Ramanujan graphs. Journal of the Ramanujan Math. Society\u00a018(1), 1\u201320 (2003)","journal-title":"Journal of the Ramanujan Math. Society"},{"issue":"3","key":"29_CR14","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A. Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica\u00a08(3), 261\u2013277 (1988)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:46Z","timestamp":1619493586000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11786986_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}