{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T02:00:23Z","timestamp":1760061623176},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_32","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"372-383","source":"Crossref","is-referenced-by-count":8,"title":["Lower Bounds for Splittings by Linear Combinations"],"prefix":"10.1007","author":[{"given":"Dmitry","family":"Itsykson","sequence":"first","affiliation":[]},{"given":"Dmitry","family":"Sokolov","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-3","key":"32_CR1","doi-asserted-by":"crossref","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."},{"issue":"3","key":"32_CR2","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1137\/060654645","volume":"37","author":"P. Beame","year":"2007","unstructured":"Beame, P., Pitassi, T., Segerlind, N.: Lower bounds for lov\u00e1sz-schrijver systems and beyond follow from multiparty communication complexity. SIAM Journal on Computing\u00a037(3), 845\u2013869 (2007)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"32_CR3","doi-asserted-by":"crossref","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"},{"issue":"1","key":"32_CR4","doi-asserted-by":"crossref","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":"32_CR5","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Communications of the ACM\u00a05, 394\u2013397 (1962)","journal-title":"Communications of the ACM"},{"key":"32_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"Davis, M., Putnam, H.: A computing procedure for quantification theory. Journal of the ACM\u00a07, 201\u2013215 (1960)","journal-title":"Journal of the ACM"},{"key":"32_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/978-3-642-22993-0_25","volume-title":"Mathematical Foundations of Computer Science 2011","author":"E. Demenkov","year":"2011","unstructured":"Demenkov, E., Kulikov, A.S.: An elementary proof of a 3n \u2212 o(n) lower bound on the circuit complexity of affine dispersers. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol.\u00a06907, pp. 256\u2013265. Springer, Heidelberg (2011)"},{"key":"32_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/978-3-642-20712-9_11","volume-title":"Computer Science \u2013 Theory and Applications","author":"D. Itsykson","year":"2011","unstructured":"Itsykson, D., Sokolov, D.: The complexity of inversion of explicit goldreich\u2019s function by DPLL algorithms. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 134\u2013147. Springer, Heidelberg (2011)"},{"issue":"2","key":"32_CR9","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/s00224-013-9514-8","volume":"54","author":"D. Itsykson","year":"2014","unstructured":"Itsykson, D.: Lower bound on average-case complexity of inversion of goldreich\u2019s function by drunken backtracking algorithms. Theory Comput. Syst.\u00a054(2), 261\u2013276 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"32_CR10","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schintger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discret. Math.\u00a05(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"32_CR11","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, New York (1997)"},{"issue":"3","key":"32_CR12","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1016\/j.apal.2008.04.001","volume":"155","author":"R. Raz","year":"2008","unstructured":"Raz, R., Tzameret, I.: Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Logic\u00a0155(3), 194\u2013224 (2008)","journal-title":"Ann. Pure Appl. Logic"},{"key":"32_CR13","unstructured":"Razborov, A.A.: Pseudorandom generators hard for k-dnf resolution and polynomial calculus resolution. Technical report (2003)"},{"issue":"2","key":"32_CR14","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00037-013-0067-7","volume":"22","author":"K. Seto","year":"2013","unstructured":"Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Computational Complexity\u00a022(2), 245\u2013274 (2013)","journal-title":"Computational Complexity"},{"key":"#cr-split#-32_CR15.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#-32_CR15.2","unstructured":"English translation of this volume: Consultants Bureau, N.Y., pp. 115-125 (1970)"},{"issue":"1-3","key":"32_CR16","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s11225-011-9356-9","volume":"99","author":"A. Urquhart","year":"2011","unstructured":"Urquhart, A.: The depth of resolution proofs. Studia Logica\u00a099(1-3), 249\u2013364 (2011)","journal-title":"Studia Logica"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T15:12:59Z","timestamp":1558969979000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}