{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:26:31Z","timestamp":1725456391135},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540645702"},{"type":"electronic","value":"9783540693536"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0028012","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T07:02:06Z","timestamp":1132642926000},"page":"149-156","source":"Crossref","is-referenced-by-count":16,"title":["Resolution and the weak pigeonhole principle"],"prefix":"10.1007","author":[{"given":"Sam","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,15]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, The complexity of the pigeonhole principle, in Proceedings of the 29-th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 346\u2013355.","DOI":"10.1109\/SFCS.1988.21951"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"P. Beame, R. Impagliazzo, J. Kraj\u00ed\u010dek, T. Pitassi, P. Pudl\u00e1k, and A. Woods, Exponential lower bounds for the pigeonhole principle, in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 200\u2013220.","DOI":"10.1145\/129712.129733"},{"key":"9_CR3","doi-asserted-by":"crossref","first-page":"916","DOI":"10.2307\/2273826","volume":"52","author":"S. R. Buss","year":"1987","unstructured":"S. R. Buss, Polynomial size proofs of the propositional pigeonhole principle, Journal of Symbolic Logic, 52 (1987), pp. 916\u2013927.","journal-title":"Journal of Symbolic Logic"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(88)90072-2","volume":"62","author":"S. R. Buss","year":"1988","unstructured":"S. R. Buss and Gy\u00f6rgy Tur\u00e1n, Resolution proofs of generalized pigeonhole principles, Theoretical Computer Science, 62 (1988), pp. 311\u2013317.","journal-title":"Theoretical Computer Science"},{"key":"9_CR5","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. A. Cook","year":"1979","unstructured":"S. A. Cook and R. A. Reckhow, The relative efficiency of propositional proof systems, Journal of Symbolic Logic, 44 (1979), pp. 36\u201350.","journal-title":"Journal of Symbolic Logic"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken, The intractability of resolution, Theoretical Computer Science, 39 (1985), pp. 297\u2013308.","journal-title":"Theoretical Computer Science"},{"key":"9_CR7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J. Krajicek","year":"1995","unstructured":"J. Krajicek, P. Pudl\u00e1k, and A. Woods, Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle, Random Structures and Algorithms, 7 (1995), pp. 15\u201339.","journal-title":"Random Structures and Algorithms"},{"key":"9_CR8","unstructured":"J. B. Paris and A. J. Wilkie, \u03940 sets and induction, in Open Days in Model Theory and Set Theory, W. Guzicki, W. Marek, A. Pelc, and C. Rauszer, eds., 1981, pp. 237\u2013248."},{"key":"9_CR9","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1017\/S0022481200028061","volume":"53","author":"J. B. Paris","year":"1988","unstructured":"J. B. Paris, A. J. WILKIE, and A. R. Woods, Provability of the pigeonhole principle and the existence of infinitely many primes, Journal of Symbolic Logic, 53 (1988), pp. 1235\u20131244.","journal-title":"Journal of Symbolic Logic"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T. Pitassi","year":"1993","unstructured":"T. Pitassi, P. Beame, and R. Impagliazzo, Exponential lower bounds for the pigeonhole principle, Computational Complexity, 3 (1993), pp. 97\u2013140.","journal-title":"Computational Complexity"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"A. Razborov, A. Widgerson and A. Yao, Read-once branching programs, rectangular proofs of the pigeon-hole principle and the transversal calculus, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 739\u2013748.","DOI":"10.1145\/258533.258673"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T02:51:18Z","timestamp":1586573478000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028012"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540645702","9783540693536"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/bfb0028012","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}