{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:49:58Z","timestamp":1759146598550},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434535"},{"type":"electronic","value":"9783540460114"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-46011-x_8","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T22:54:16Z","timestamp":1182207256000},"page":"100-116","source":"Crossref","is-referenced-by-count":14,"title":["Proof Complexity of Pigeonhole Principles"],"prefix":"10.1007","author":[{"given":"Alexander A.","family":"Razborov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,19]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2178\/bsl\/1203350879","volume":"1","author":"A. Urquhart","year":"1995","unstructured":"Urquhart, A.: The complexity of propositional proofs. Bulletin of Symbolic Logic 1 (1995) 425\u2013467","journal-title":"Bulletin of Symbolic Logic"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J.: Bounded arithmetic, propositional logic and complexity theory. Cambridge University Press (1995)","DOI":"10.1017\/CBO9780511529948"},{"key":"8_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/3-540-61440-0_116","volume-title":"Lower bounds for propositional proofs and independence results in Bounded Arithmetic","author":"A. Razborov","year":"1996","unstructured":"Razborov, A.: Lower bounds for propositional proofs and independence results in Bounded Arithmetic. In auf der Heide, F.M., Monien, B., eds.: Proceedings of the 23rd ICALP, Lecture Notes in Computer Science, 1099, NewYork\/Berlin, Springer-Verlag (1996) 48\u201362"},{"key":"8_CR4","unstructured":"Beame, P., Pitassi, T.: Propositional proof complexity: Past, present and future. Technical Report TR98-067, Electronic Colloquium on Computational Complexity (1998)"},{"key":"8_CR5","unstructured":"Pudl\u00e1k, P.: The lengths of proofs. In Buss, S., ed.: Handbook of Proof Theory. Elsevier (1998) 547\u2013637"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, A.R.: The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44 (1979) 36\u201350","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR7","unstructured":"Reckhow, R.A.: On the lengths of proofs in the propositional calculus. Technical Report 87, University of Toronto (1976)"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Maciel, A., Pitassi, T., Woods, A.: A new proof of the weak pigeonhole principle. Manuscript (1999)","DOI":"10.1145\/335305.335348"},{"key":"8_CR9","unstructured":"H\u00e5stad, J.: Computational limitations on Small Depth Circuits. PhD thesis, Massachusetts Institute of Technology (1986)"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Clegg, M., Edmonds, J., Impagliazzo, R.: Using the Groebner basis algorithm to find proofs of unsatisfiability. In: Proceedings of the 28th ACM STOC. (1996) 174\u2013183","DOI":"10.1145\/237814.237860"},{"key":"8_CR11","unstructured":"Ben-Sasson, E., Wigderson, A.: Short proofs are narrow \u2014 resolution made simple. In: Proceedings of the 31st ACM STOC. (1999) 517\u2013526"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A., Wigderson, A.: Pseudorandom generators in propositional complexity. In: Proceedings of the 41st IEEE FOCS. (2000) 43\u201353","DOI":"10.1109\/SFCS.2000.892064"},{"key":"8_CR13","unstructured":"Razborov, A.: Improved resolution lower bounds for the weak pigeonhole principle. Technical Report TR01-055, Electronic Colloquium on Computational Complexity (2001)Available at ftp:\/\/ftp.eccc.uni-trier.de\/pub\/eccc\/reports\/2001\/TR01-055\/index.html ."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"Haken, A.: The intractability or resolution. Theoretical Computer Science 39 (1985) 297\u2013308","journal-title":"Theoretical Computer Science"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"916","DOI":"10.2307\/2273826","volume":"52","author":"S.R. Buss","year":"1987","unstructured":"Buss, S.R.: Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic 52 (1987) 916\u2013927","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0166-218X(87)90039-4","volume":"18","author":"W. Cook","year":"1987","unstructured":"Cook, W., Coullard, C.R., Tur\u00e1n, G.: On the complexity of cutting plane proofs. Discrete Applied Mathematics 18 (1987) 25\u201338","journal-title":"Discrete Applied Mathematics"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The complexity of the pigeonhole principle. In: Proceedings of the 29th IEEE Symposium on Foundations of Computer Science. (1988) 346\u2013355","DOI":"10.1109\/SFCS.1988.21951"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"1161","DOI":"10.1137\/0221068","volume":"21","author":"S. Bellantoni","year":"1992","unstructured":"Bellantoni, S., Pitassi, T., Urquhart, A.: Approximation of small depth Frege proofs. SIAM Journal on Computing 21 (1992) 1161\u20131179","journal-title":"SIAM Journal on Computing"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T. Pitassi","year":"1993","unstructured":"Pitassi, T., Beame, P., Impagliazzo, R.: Exponential lower bounds for the pigeonhole principle. Computational Complexity 3 (1993) 97\u2013140","journal-title":"Computational Complexity"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek, J., Pudl\u00e1k, P., Woods, A.R.: Exponential lower bounds to the size of bounded depth Frege proofs of the pigeonhole principle. Random Structures and Algorithms 7 (1995) 15\u201339","journal-title":"Random Structures and Algorithms"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s000370050013","volume":"7","author":"A. Razborov","year":"1998","unstructured":"Razborov, A.: Lower bounds for the polynomial calculus. Computational Complexity 7 (1998) 291\u2013324","journal-title":"Computational Complexity"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s000370050024","volume":"8","author":"R. Impagliazzo","year":"1999","unstructured":"Impagliazzo, R., Pudl\u00e1k, P., Sgall, J.: Lower bounds for the polynomial calculus and the Groebner basis algorithm. Computational Complexity 8 (1999) 127\u2013144","journal-title":"Computational Complexity"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.: Lower bounds for the polynomial calculus: non-binomial case. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. (2001) 190\u2013199","DOI":"10.1109\/SFCS.2001.959893"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Riis, S.: Independence in Bounded Arithmetic. PhD thesis, Oxford University (1993)","DOI":"10.7146\/brics.v1i23.21644"},{"key":"8_CR25","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.2307\/2274618","volume":"53","author":"J.B. Paris","year":"1988","unstructured":"Paris, J.B., Wilkie, A.J., Woods, A.R.: Provability of the pigeonhole principle and the existence of infinitely many primes. Journal of Symbolic Logic 53 (1988) 1235\u20131244","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"Kraj\u00ed\u010dek, J.: On the weak pigeonhole principle. Fundamenta Mathematicae 170 (2001) 123\u2013140","journal-title":"Fundamenta Mathematicae"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(88)90072-2","volume":"62","author":"S. Buss","year":"1988","unstructured":"Buss, S., Tur\u00e1n, G.: Resolution proofs of generalized pigeonhole principle. Theoretical Computer Science 62 (1988) 311\u2013317","journal-title":"Theoretical Computer Science"},{"key":"8_CR28","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/3-540-44683-4_14","volume-title":"Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms","author":"A. Atserias","year":"2001","unstructured":"Atserias, A.: Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms. In J. Sgall, A. Pultr, P.K., ed.: Proceedings of the 26th International Symposium on the Mathematical Foundations of Computer Science (Marianske Lazne, August\u2019 01), Lecture Notes in Computer Science 2136, Springer-Verlag (2001) 148\u2013158"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"Atserias, A., Bonet, M.L., Esteban, J.L.: Lower bounds for the weak pigeonhole principle beyond resolution. To appear in Information and Computation (2000)","DOI":"10.1007\/3-540-48224-5_81"},{"key":"8_CR30","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/BFb0028012","volume-title":"Resolution and the weak pigeonhole principle","author":"S. Buss","year":"1998","unstructured":"Buss, S., Pitassi, T.: Resolution and the weak pigeonhole principle. In: Proceedings of the CSL97, Lecture Notes in Computer Science, 1414, NewYork\/Berlin, Springer-Verlag (1997) 149\u2013156"},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"Razborov, A., Wigderson, A., Yao, A.: Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. In: Proceedings of the 29th ACM Symposium on Theory of Computing. (1997) 739\u2013748","DOI":"10.1145\/258533.258673"},{"key":"8_CR32","doi-asserted-by":"crossref","unstructured":"Pitassi, T., Raz, R.: Regular resolution lower bounds for the weak pigeonhole principle. In: Proceedings of the 33rd ACM Symposium on the Theory of Computing. (2001) 347\u2013355","DOI":"10.1145\/380752.380821"},{"key":"8_CR33","doi-asserted-by":"crossref","unstructured":"Raz, R.: Resolution lower bounds for the weak pigeonhole principle. Technical Report TR01-021, Electronic Colloquium on Computational Complexity (2001)","DOI":"10.1145\/509907.509987"},{"key":"8_CR34","unstructured":"Razborov, A.: Resolution lower bounds for the weak functional pigeonhole principle. Manuscript, available at http:\/\/www.mi.ras.ru\/~razborov\/matching.ps (2001)"},{"key":"8_CR35","unstructured":"Razborov, A.: Resolution lower bounds for perfect matching principles. Manuscript, available at http:\/\/www.mi.ras.ru\/~razborov\/matching.ps (2001)"},{"key":"8_CR36","doi-asserted-by":"crossref","unstructured":"Razborov, A.: Bounded Arithmetic and lower bounds in Boolean complexity. In Clote, P., Remmel, J., eds.: Feasible Mathematics II. Progress in Computer Science and Applied Logic, vol. 13. Birkh\u00e4user (1995) 344\u2013386","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"8_CR37","doi-asserted-by":"crossref","unstructured":"Dantchev, S., Riis, S.: \u201cPlanar\u201d tautologies hard for Resolution. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. (2001) 220\u2013229","DOI":"10.1109\/SFCS.2001.959896"},{"key":"8_CR38","unstructured":"Alekhnovich, M.: Mutilated chessboard is exponentially hard for resolution. Manuscript (2000)"},{"key":"8_CR39","doi-asserted-by":"crossref","unstructured":"Beame, P., Riis, S.: More on the relative strength of counting principles. In Beame, P., Buss, S., eds.: Proof Complexity and Feasible Arithmetics: DIMACS workshop, April 21\u201324, 1996, DIMACS Series in Dicrete Mathematics and Theoretical Computer Science, vol. 39. American Math. Soc. (1997) 13\u201335","DOI":"10.1090\/dimacs\/039\/02"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46011-X_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T04:23:49Z","timestamp":1556511829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46011-X_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434535","9783540460114"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/3-540-46011-x_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}