{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:42:04Z","timestamp":1747546924931},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540665366"},{"type":"electronic","value":"9783540481683"}],"license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48168-0_26","type":"book-chapter","created":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T06:30:26Z","timestamp":1196490626000},"page":"362-373","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Lower Bounds for Space in Resolution"],"prefix":"10.1007","author":[{"given":"Jacobo","family":"Tor\u00e1n","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov A. and Wigderson, A.: Space complexity in Propositional Calculus. Preliminary draft, July 1999.","DOI":"10.1145\/335305.335347"},{"key":"26_CR2","unstructured":"Beame, P. and Pitassi, T.: Simplified and Improved Resolution Lower Bounds. In Proc. 37th IEEE Symp. on Foundations of Computer Science, (1996) 274\u2013282."},{"key":"26_CR3","unstructured":"Ben-Sasson, E. and Widgerson, A.: Short proofs are narrow, resolution made simple. In Proc. 31st ACM Symp. on Theory of Computing (1999) 517\u2013527."},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Buss, S. and Pitassi, T.: Resolution and theWeak Pigeonhole Principle. In Computer Science Logic 97, (1997), proceedings to appear in Springer Verlag.","DOI":"10.1007\/BFb0028012"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"Chv\u00e1tal, V. and Szemer\u00e9di, E.: Many hard examples for resolution. Journal of the ACM, 35 (1988) 759\u2013768.","journal-title":"Journal of the ACM"},{"key":"26_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/3-540-49116-3_52","volume-title":"Proc. 16th STACS","author":"J.L. Esteban","year":"1999","unstructured":"Esteban, J.L. and Tor\u00e1n, J.: Space bounds for resolution. In Proc. 16th STACS, Springer Verlag LNCS 1563 (1999) 551\u2013561."},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"35","author":"A. Haken","year":"1985","unstructured":"Haken, A: The intractability of resolution Theoretical Computer Science 35 (1985) 297\u2013308.","journal-title":"Theoretical Computer Science"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Kleine B\u00fcning, H. and Lettman, T.: Aussangenlogik: Deduktion und Algorithmen, B.G. Teubner Stuttgart (1994).","DOI":"10.1007\/978-3-322-84809-3"},{"key":"26_CR9","first-page":"71","volume":"9","author":"A. Margulis","year":"1973","unstructured":"Margulis, A.: Explicit construction of concentrators. Problems Information Transmission 9 (1973) 71\u201380.","journal-title":"Problems Information Transmission"},{"key":"26_CR10","unstructured":"Messner, J.: Personal communication 1999."},{"key":"26_CR11","unstructured":"Sch\u00f6ning, U.: Better expanders and superconcentrators by Kolmogorov complexity. In Proceedings 4th International Colloquium on Structural Information and Communication Complexity, Sirocco 97 Carleton Scientific (1997) 138\u2013151."},{"key":"26_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/BFb0029954","volume-title":"Proc. 22nd MFCS Conference","author":"U. Sch\u00f6ning","year":"1997","unstructured":"Sch\u00f6ning, U.: Resolution proofs, exponential bounds and Kolmogorov complexity. In Proc. 22nd MFCS Conference, Springer Verlag LNCS 1295 (1997) 110\u2013116."},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Tseitin, G.S. On the complexity of derivation in propositional calculus. In Studies in Constructive Mathematics and Mathematical Logic, Part 2. Consultants Bureau (1968) 115\u2013125.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"26_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. Journal of the ACM 34 (1987) 209\u2013219.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48168-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,6]],"date-time":"2020-04-06T00:09:10Z","timestamp":1586131750000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48168-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540665366","9783540481683"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-48168-0_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1999]]},"assertion":[{"value":"13 May 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}