{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T22:51:20Z","timestamp":1762210280682},"reference-count":21,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,6,1]],"date-time":"2003-06-01T00:00:00Z","timestamp":1054425600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3735,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2003,6]]},"DOI":"10.1016\/s0304-3975(02)00453-x","type":"journal-article","created":{"date-parts":[[2003,1,21]],"date-time":"2003-01-21T14:54:09Z","timestamp":1043160849000},"page":"233-243","source":"Crossref","is-referenced-by-count":22,"title":["Resolution lower bounds for the weak functional pigeonhole principle"],"prefix":"10.1016","volume":"303","author":[{"given":"Alexander A.","family":"Razborov","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(02)00453-X_BIB1","doi-asserted-by":"crossref","unstructured":"M. Alekhnovich, E. Ben-Sasson, A. Razborov, A. Wigderson, Pseudorandom generators in propositional complexity, in: Proc. 41st IEEE FOCS, 2000, pp. 43\u201353.","DOI":"10.1109\/SFCS.2000.892064"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB2","doi-asserted-by":"crossref","unstructured":"P. Beame, T. Pitassi, Simplified and improved resolution lower bounds, in: Proc. 37th IEEE FOCS, 1996, pp. 274\u2013282.","DOI":"10.1109\/SFCS.1996.548486"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB3","unstructured":"P. Beame, T. Pitassi, Propositional proof complexity: past, present and future, Technical Report TR98-067, Electronic Colloquium on Computational Complexity, 1998."},{"issue":"2","key":"10.1016\/S0304-3975(02)00453-X_BIB4","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/375827.375835","article-title":"Short proofs are narrow\u2014resolution made simple","volume":"48","author":"Ben-Sasson","year":"2001","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB5","unstructured":"A. Blake, Canonical expressions in Boolean algebra, Ph.D. Thesis, University of Chicago, 1937."},{"key":"10.1016\/S0304-3975(02)00453-X_BIB6","series-title":"Proc. CSL97","first-page":"149","article-title":"Resolution and the weak pigeonhole principle","volume":"Vol. 1414","author":"Buss","year":"1997"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB7","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/0304-3975(88)90072-2","article-title":"Resolution proofs of generalized pigeonhole principle","volume":"62","author":"Buss","year":"1988","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"10.1016\/S0304-3975(02)00453-X_BIB8","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/48014.48016","article-title":"Many hard examples for resolution","volume":"35","author":"Chv\u00e1tal","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB9","doi-asserted-by":"crossref","unstructured":"M. Clegg, J. Edmonds, R. Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, in: Proc. 28th ACM STOC, 1996, pp. 174\u2013183.","DOI":"10.1145\/237814.237860"},{"issue":"3","key":"10.1016\/S0304-3975(02)00453-X_BIB10","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB11","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","article-title":"The intractability or resolution","volume":"39","author":"Haken","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(02)00453-X_BIB12","series-title":"Proof Complexity and Feasible Arithmetics: DIMACS Workshop, April 21\u201324, 1996","first-page":"163","article-title":"Exponential lower bounds for semantic resolution","volume":"Vol. 39","author":"Jukna","year":"1997"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB13","doi-asserted-by":"crossref","unstructured":"T. Pitassi, R. Raz, Regular resolution lower bounds for the weak pigeonhole principle, in: Proc. 33rd ACM Symp. on the Theory of Computing, 2001, pp. 347\u2013355.","DOI":"10.1145\/380752.380821"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB14","doi-asserted-by":"crossref","unstructured":"R. Raz, Resolution lower bounds for the weak pigeonhole principle, Technical Report TR01-021, Electronic Colloquium on Computational Complexity, 2001.","DOI":"10.1145\/509907.509987"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB15","series-title":"Proc. 23rd ICALP","first-page":"48","article-title":"Lower bounds for propositional proofs and independence results in bounded arithmetic","volume":"Vol. 1099","author":"Razborov","year":"1996"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB16","unstructured":"A. Razborov, 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":"10.1016\/S0304-3975(02)00453-X_BIB17","unstructured":"A. Razborov, Resolution lower bounds for perfect matching principles, Manuscript, available at http:\/\/www.mi.ras.ru\/~razborov\/matching.ps, 2001."},{"key":"10.1016\/S0304-3975(02)00453-X_BIB18","doi-asserted-by":"crossref","unstructured":"A. Razborov, A. Wigderson, A. Yao, Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus, in: Proc. 29th ACM Symp. on Theory of Computing, 1997, pp. 739\u2013748.","DOI":"10.1145\/258533.258673"},{"issue":"1","key":"10.1016\/S0304-3975(02)00453-X_BIB19","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/321250.321253","article-title":"A machine-oriented logic based on the resolution principle","volume":"12","author":"Robinson","year":"1965","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(02)00453-X_BIB20","unstructured":"G.C. Tseitin, On the complexity of derivations in propositional calculus, in: Studies in Constructive Mathematics and Mathematical Logic, Part II, Consultants Bureau, New York, London, 1968."},{"issue":"1","key":"10.1016\/S0304-3975(02)00453-X_BIB21","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/7531.8928","article-title":"Hard examples for resolution","volume":"34","author":"Urquhart","year":"1987","journal-title":"J. ACM"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750200453X?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S030439750200453X?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T02:13:58Z","timestamp":1583979238000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S030439750200453X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,6]]}},"alternative-id":["S030439750200453X"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(02)00453-x","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}