{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:47:37Z","timestamp":1759146457474},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_14","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"162-173","source":"Crossref","is-referenced-by-count":2,"title":["Graph Expansion, Tseitin Formulas and Resolution Proofs for CSP"],"prefix":"10.1007","author":[{"given":"Dmitry","family":"Itsykson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vsevolod","family":"Oparin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"14_CR1","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s10817-005-9006-x","volume":"35","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M., Hirsch, E.A., Itsykson, D.: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. J. Autom. Reason.\u00a035(1-3), 51\u201372 (2005)","journal-title":"J. Autom. Reason."},{"key":"14_CR2","unstructured":"Baker, A.B.: Intelligent backtracking on constraint satisfaction problems: Experimental and theoretical results (1995)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Buss, S., Grigoriev, D., Impagliazzo, R., Pitassi, T.: Linear gaps between degrees for the polynomial calculus modulo distinct primes. Journal of Computer and System Sciences, 547\u2013556 (1999)","DOI":"10.1145\/301250.301399"},{"issue":"2","key":"14_CR4","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow \u2014 resolution made simple. Journal of ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"Journal of ACM"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-642-00457-5_31","volume-title":"Theory of Cryptography","author":"J. Cook","year":"2009","unstructured":"Cook, J., Etesami, O., Miller, R., Trevisan, L.: Goldreich\u2019s one-way function candidate and myopic backtracking algorithms. In: Reingold, O. (ed.) TCC 2009. LNCS, vol.\u00a05444, pp. 521\u2013538. Springer, Heidelberg (2009)"},{"key":"14_CR6","unstructured":"Hwang, C.Y.J.: A Theoretical Comparison of Resolution Proof Systems for CSP Algorithms. Master\u2019s thesis, Simon Fraser University (2004)"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s000370050024","volume":"8","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Pudlak, P., Sgall, J.: Lower bounds for the polynomial calculus and the grobner basis algorithm. Computational Complexity\u00a08, 127\u2013144 (1997)","journal-title":"Computational Complexity"},{"key":"14_CR8","first-page":"88","volume":"399","author":"D. Itsykson","year":"2012","unstructured":"Itsykson, D., Sokolov, D.: The complexity of inversion of explicit Goldreichs function by DPLL algorithms. Zapiski nauchnyh seminarov POMI\u00a0399, 88\u2013109 (2012)","journal-title":"Zapiski nauchnyh seminarov POMI"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/978-3-642-13182-0_19","volume-title":"Computer Science \u2013 Theory and Applications","author":"D. Itsykson","year":"2010","unstructured":"Itsykson, D.: Lower bound on average-case complexity of inversion of goldreich\u2019s function by drunken backtracking algorithms. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol.\u00a06072, pp. 204\u2013215. Springer, Heidelberg (2010)"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Mitchell, D.G.: The resolution complexity of constraint satisfaction (2002)","DOI":"10.1007\/3-540-46135-3_20"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/3-540-46135-3_20","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"D.G. Mitchell","year":"2002","unstructured":"Mitchell, D.G.: Resolution complexity of random constraints. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 295\u2013309. Springer, Heidelberg (2002)"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/978-3-540-45193-8_38","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"D.G. Mitchell","year":"2003","unstructured":"Mitchell, D.G.: Resolution and constraint satisfaction. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 555\u2013569. Springer, Heidelberg (2003)"},{"key":"#cr-split#-14_CR13.1","unstructured":"Tseitin, G.S.: On the complexity of derivation in the propositional calculus. Zapiski Nauchnykh Seminarov LOMI\u00a08, 234-259 (1968)"},{"key":"#cr-split#-14_CR13.2","unstructured":"English translation of this volume: Consultants Bureau, N.Y., pp. 115-125 (1970)"},{"issue":"1","key":"14_CR14","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"Urquhart, A.: Hard examples for resolution. JACM\u00a034(1), 209\u2013219 (1987)","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T16:23:19Z","timestamp":1557764599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}