{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:35:40Z","timestamp":1742978140876,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_32","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"387-398","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Optimal Lower Bound for Resolution with 2-Conjunctions"],"prefix":"10.1007","author":[{"given":"Jan","family":"Johannsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"A. Atserias and M. L. Bonet. On the automatizability of resolution and related propositional proof systems. Technical Report ECCC TR02-010, Electronic Colloquium on Computational Complexity, 2002.","DOI":"10.1007\/3-540-45793-3_38"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"A. Atserias, M. L. Bonet, and J. L. Esteban. Lower bounds for the weak pigeonhole principle beyond resolution, 2002. To appear in Information and Computation. Preliminary Version in Proc. 28th International Colloquium on Automata Languages and Programming, 2001.","DOI":"10.1007\/3-540-48224-5_81"},{"key":"32_CR3","unstructured":"R. Beigel and D. Eppstein. 3-coloring in time O(1.3446n): a no-MIS algorithm. In Proc. 36th IEEE Symposiom on Foundations of Computer Science, pages 444\u2013452, 1995."},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson. Hard examples for bounded-depth Frege. To appear in Proc. 34th ACM Symposium on Theory of Computing, 2002.","DOI":"10.1145\/509907.509988"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"E. Ben-Sasson and A. Wigderson. Short proofs are narrow \u2014 resolution made simple. Journal of the ACM, 48:149\u2013169, 2001. Preliminary Version in Proc. 31st Symposium on Theory of Computing, 1999.","journal-title":"Journal of the ACM"},{"key":"32_CR6","unstructured":"B. Bollob\u00e1s. Random Graphs. Academic Press, 1985."},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"J. Kraj\u00ed\u010dek. On the weak pigeonhole principle. Fundamenta Mathematicae, 170:123\u2013140, 2001.","journal-title":"Fundamenta Mathematicae"},{"key":"32_CR8","unstructured":"N. Segerlind, S. R. Buss, and R. Impagliazzo. A switching lemma for small restrictions and lower bounds for k-DNF resolution. Submitted for publication, 2002."},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"G. Tseitin. On the complexity of derivation in propositional calculus. In A. O. Slisenko, editor, Studies in Constructive Mathematics and Mathematical Logic, Part 2, pages 115\u2013125. Consultants Bureau, 1970.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/7531.8928","volume":"34","author":"A. Urquhart","year":"1987","unstructured":"A. Urquhart. Hard examples for resolution. Journal of the ACM, 34:209\u2013219, 1987.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T21:19:01Z","timestamp":1674163141000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_32","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}