{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:26:28Z","timestamp":1737523588494,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_81","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"1005-1016","source":"Crossref","is-referenced-by-count":6,"title":["Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution"],"prefix":"10.1007","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mar\u00eca Luisa","family":"Bonet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan Luis","family":"Esteban","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"issue":"1","key":"81_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579196","volume":"7","author":"N. Alon","year":"1987","unstructured":"N. Alon and R. Boppana. The monotone circuit complexity of boolean functions. Combinatorica, 7(1):1\u201322, 1987.","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"P. Beame, R. Impagliazzo, J. Kraj\u00ec\u010dek, T. Pitassi, P. Pudl\u00e1k, and A. Woods. Exponential lower bounds for PHP. In STOC92, pages 200\u2013220, 1992.","key":"81_CR2","DOI":"10.1145\/129712.129733"},{"unstructured":"P. Beame, R. Karp, T. Pitassi, and M. Saks. The efficiency of resolution and Davis-Putnam procedures. Submitted. Previous version in STOC\u201998, 1999.","key":"81_CR3"},{"doi-asserted-by":"crossref","unstructured":"P. Beame and T. Pitassi. Simplified and improved resolution lower bounds. In FOCS96, pages 274\u2013282, 1996.","key":"81_CR4","DOI":"10.1109\/SFCS.1996.548486"},{"unstructured":"E. Ben-Sasson and A. Wigderson. Short proofs are narrow: Resolution made simple. In STOC99, pages 517\u2013527, 1999. Revised version (2000).","key":"81_CR5"},{"issue":"3","key":"81_CR6","doi-asserted-by":"publisher","first-page":"708","DOI":"10.2307\/2275569","volume":"62","author":"M. Bonet","year":"1997","unstructured":"M. Bonet, T. Pitassi, and R. Raz. Lower bounds for cutting planes proofs with small coefficients. The Journal of Symbolic Logic, 62(3):708\u2013728, Sept. 1997.","journal-title":"The Journal of Symbolic Logic"},{"key":"81_CR7","series-title":"Lect Notes Comput Sci","volume-title":"CSL: 11th Workshop on Computer Science Logic","author":"S. Buss","year":"1997","unstructured":"S. Buss and T. Pitassi. Resolution and the weak pigeonhole principle. In CSL: 11th Workshop on Computer Science Logic. LNCS, Springer-Verlag, 1997."},{"issue":"4","key":"81_CR8","doi-asserted-by":"publisher","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. The Journal of Symbolic Logic, 52(4):916\u2013927, Dec. 1987.","journal-title":"The Journal of Symbolic Logic"},{"issue":"3","key":"81_CR9","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 G. Tur\u00e1n. Resolution proofs on generalized pigeonhole principles. Theoretical Computer Science, 62(3):311\u2013317, Dec. 1988.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"81_CR10","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1145\/48014.48016","volume":"35","author":"V. Chv\u00e1tal","year":"1988","unstructured":"V. Chv\u00e1tal and E. Szemer\u00e9di. Many hard examples for resolution. J. ACM, 35(4):759\u2013768, 1988.","journal-title":"J. ACM"},{"unstructured":"G. Grimmet and D. Stirzaker. Probability and Random Processes. Oxford, 1982.","key":"81_CR11"},{"issue":"2-3","key":"81_CR12","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. TCS, 39(2-3):297\u2013308, Aug. 1985.","journal-title":"TCS"},{"unstructured":"J. Kraj\u00ec\u010dek. On the weak PHP. To appear in Fundamenta Mathematic\u00e6, 2000.","key":"81_CR13"},{"doi-asserted-by":"crossref","unstructured":"A. Maciel, T. Pitassi, and A. Woods. A new proof of the weak pigeonhole principle. In STOC00, pages 368\u2013377, 2000.","key":"81_CR14","DOI":"10.1145\/335305.335348"},{"issue":"4","key":"81_CR15","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.2307\/2274618","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. The Journal of Symbolic Logic, 53(4):1235\u20131244, 1988.","journal-title":"The Journal of Symbolic Logic"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_81","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:14Z","timestamp":1737503414000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_81"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_81","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}