{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T20:04:10Z","timestamp":1777579450875,"version":"3.51.4"},"reference-count":17,"publisher":"Duke University Press","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1996,10,1]]},"DOI":"10.1305\/ndjfl\/1040046140","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T21:12:48Z","timestamp":1046207568000},"source":"Crossref","is-referenced-by-count":19,"title":["Simplified Lower Bounds for Propositional Proofs"],"prefix":"10.1215","volume":"37","author":[{"given":"Xudong","family":"Fu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alasdair","family":"Urquhart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., \u201cThe complexity of the pigeonhole principle,\" pp. 346\u2013355 in <i>Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science<\/i>, IEEE Computer Society Press, 1988. Zbl 0811.03042 MR 96a:03065","DOI":"10.1109\/SFCS.1988.21951"},{"key":"2","unstructured":"Beame, P. \u201cA switching lemma primer,\" preprint, 1993."},{"key":"3","doi-asserted-by":"crossref","unstructured":"Beame, P., R. Impagliazzo, J. Kraj\u00ed\u010dek, T. Pitassi, P. Pudl\u00e1k, and A. Woods, \u201cExponential lower bounds for the pigeonhole principle,\" pp. 200\u2013220 in <i>Proceedings of the 24th Annual ACM Symposium on the Theory of Computing<\/i>, ACM Press, 1992. Zbl 0784.03034 MR 94f:03019","DOI":"10.1145\/129712.129733"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Bellantoni, S., T. Pitassi, and A. Urquhart, \u201cApproximation and small-depth Frege proofs,\" <i>SIAM Journal of Computing<\/i>, vol. 21 (1992), pp. 1161\u20131179. Zbl 0762.03020 MR 93m:03095","DOI":"10.1137\/0221068"},{"key":"5","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., and E. Szemer\u00e9di, \u201cMany hard examples for resolution,\u201d <i>Journal of the Association for Computing Machinery<\/i>, vol. 35 (1988), pp. 759\u2013768. Zbl 0712.03008 MR 91f:68182","DOI":"10.1145\/48014.48016"},{"key":"6","unstructured":"Cook, S. A., <i>Resolution Lower Bound for Complete Graph Clauses<\/i>, manuscript, University of Toronto, Toronto, 1993."},{"key":"7","doi-asserted-by":"crossref","unstructured":"Furst, M., J. B. Saxe, and M. Sipser, \u201cParity, circuits, and the polynomial-time hierarchy,\u201d pp. 260\u2013270 in <i>Proceedings of the 22nd Annual IEEE Symposium on the Foundations of Computer Science<\/i>, IEEE Computer Society Press, 1981. Zbl 0534.94008 MR 86e:68048","DOI":"10.1109\/SFCS.1981.35"},{"key":"8","unstructured":"Frege, G., <i>Begriffsschrift, eine der arithmetischen nachgebildete F<\/i>ormelsprache des reinen Denkens, Nebert, Halle, 1879."},{"key":"9","unstructured":"H\u00e5 stad, J. T., <i>Computational Limitations of Small-Depth Circuits<\/i>, MIT Press, Cambridge, 1987."},{"key":"10","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J., P. Pudl\u00e1k, and A. Woods, \u201cExponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle,\" <i>Random Structures and Algorithms<\/i>, vol. 7 (1995), pp. 15\u201339. Zbl 0843.03032 MR 96i:03053","DOI":"10.1002\/rsa.3240070103"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Von Neumann, J., \u201cZur Hilbertschen Beweistheorie,\" <i>Mathematische Zeitschrift<\/i>, vol. 26 (1926), pp. 1\u201346.","DOI":"10.1007\/BF01475439"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Pitassi. T., P. Beame, and R. Impagliazzo, \u201cExponential lower bounds for the pigeonhole principle,\" <i>Computational Complexity<\/i>, vol. 3 (1993), pp. 97\u2013140. Zbl 0784.03034 MR \u00ca94f:03019","DOI":"10.1007\/BF01200117"},{"key":"13","doi-asserted-by":"crossref","unstructured":"Razborov, A. A., \u201cBounded arithmetic and lower bounds in Boolean complexity,\u201d pp. 344\u2013386 in <i>Feasible Mathematics II<\/i>, edited by P. Clote and J. Remmel, Birkh\u00e4user, Boston, 1995. Zbl 0838.03044 MR 96d:03057","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"14","unstructured":"Shoenfield, J., <i>Mathematical Logic<\/i>, Addison-Wesley, Reading, 1967. Zbl 0965.03001 MR 2001h:03003"},{"key":"15","doi-asserted-by":"crossref","unstructured":"Tseitin, G. S., \u201cOn the complexity of derivation in propositional calculus,\" pp. 115\u2013125 in <i>Studies in Constructive Mathematics and Mathematical Logic, Part 2<\/i>, edited by A. O. Slisenko, 1970 (reprinted in <i>Automation of Reasoning Vol. 2<\/i>, edited by J. Siekmann and G. Wrightson, Springer-Verlag, New York, 1983, pp. 466\u2013483). Zbl 0567.03002","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Urquhart, A., \u201cHard examples for resolution,\u201d <i>Journal of the Association for Computing Machinery<\/i>, vol. 34 (1987), pp. 209\u2013219. Zbl 0639.68093 MR 89e:68056","DOI":"10.1145\/7531.8928"},{"key":"17","doi-asserted-by":"crossref","unstructured":"Yao, A., \u201cSeparating the polynomial-time hierarchy by oracles,\u201d pp. 1\u201310 in <i>Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Science<\/i>, IEEE Computer Society Press, 1985.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1040046140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,11]],"date-time":"2024-12-11T21:49:52Z","timestamp":1733953792000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-37\/issue-4\/Simplified-Lower-Bounds-for-Propositional-Proofs\/10.1305\/ndjfl\/1040046140.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,10,1]]},"references-count":17,"journal-issue":{"issue":"4","published-online":{"date-parts":[[1996,10,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1040046140","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[1996,10,1]]}}}