{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:46Z","timestamp":1750307566884,"version":"3.41.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,5,1]],"date-time":"2010-05-01T00:00:00Z","timestamp":1272672000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2010,5]]},"abstract":"<jats:p>We present a simple proof of the bounded-depth Frege proof lower bounds of Pitassi et al. [1993] and Kraj\u00ed\u010dek et al. [1995] for the pigeonhole principle. Our method uses the interpretation of proofs as two player games given by Pudl\u00e1k and Buss. Our lower bound is conceptually simpler than previous ones, and relies on tools and intuition that are well known in the context of computational complexity. This makes the lower bound of Pitassi et al. [1993] and Kraj\u00ed\u010dek et al. [1995] accessible to the general computational complexity audience. We hope this new view will open new directions for research in proof complexity.<\/jats:p>","DOI":"10.1145\/1740582.1740587","type":"journal-article","created":{"date-parts":[[2010,5,18]],"date-time":"2010-05-18T13:46:22Z","timestamp":1274190382000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Lower bounds for bounded depth Frege proofs via Pudl\u00e1k-Buss games"],"prefix":"10.1145","volume":"11","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prahladh","family":"Harsha","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21951"},{"volume-title":"A switching lemma primer. Tech. rep. UW-CSE-95-07-01","author":"Beame P.","key":"e_1_2_1_3_1","unstructured":"Beame , P. 1994. A switching lemma primer. Tech. rep. UW-CSE-95-07-01 . University of Washington , Seattle, WA . Beame, P. 1994. A switching lemma primer. Tech. rep. UW-CSE-95-07-01. University of Washington, Seattle, WA."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221068"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703433146"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294258"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.35"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"volume-title":"Advances in Computing Research","author":"H\u00e5stad J.","key":"e_1_2_1_10_1","unstructured":"H\u00e5stad , J. 1989. Almost optimal lower bounds for small depth circuits . In Randomness and Computation, S. Micali, Ed. Advances in Computing Research , vol. 5 . JAI Press , Greenwich, CT , 143--170. H\u00e5stad, J. 1989. Almost optimal lower bounds for small depth circuits. In Randomness and Computation, S. Micali, Ed. Advances in Computing Research, vol. 5. JAI Press, Greenwich, CT, 143--170."},{"volume-title":"Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and its Applications","author":"Kraj\u00ed\u010dek J.","key":"e_1_2_1_11_1","unstructured":"Kraj\u00ed\u010dek , J. 1995. Bounded Arithmetic , Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and its Applications , vol. 60 . Cambridge University Press , Cambridge, U.K. Kraj\u00ed\u010dek, J. 1995. Bounded Arithmetic, Propositional Logic, and Complexity Theory. Encyclopedia of Mathematics and its Applications, vol. 60. Cambridge University Press, Cambridge, U.K."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 8th International Workshop, Conference for Computer Science Logic (CSL) (25--30 Sept.), L. Pacholski and J. Tiuryn, Eds. Lecture Notes in Computer Science","volume":"933","author":"Pudl\u00e1k P.","unstructured":"Pudl\u00e1k , P. and Buss , S. R . 1994. How to lie without being (easily) convicted and the length of proofs in propositional calculus . In Proceedings of the 8th International Workshop, Conference for Computer Science Logic (CSL) (25--30 Sept.), L. Pacholski and J. Tiuryn, Eds. Lecture Notes in Computer Science , vol. 933 . Springer, Berlin, Germany, 151--162. Pudl\u00e1k, P. and Buss, S. R. 1994. How to lie without being (easily) convicted and the length of proofs in propositional calculus. In Proceedings of the 8th International Workshop, Conference for Computer Science Logic (CSL) (25--30 Sept.), L. Pacholski and J. Tiuryn, Eds. Lecture Notes in Computer Science, vol. 933. Springer, Berlin, Germany, 151--162."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050013"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1040046140"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1740582.1740587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1740582.1740587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:55Z","timestamp":1750250455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1740582.1740587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,5]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["10.1145\/1740582.1740587"],"URL":"https:\/\/doi.org\/10.1145\/1740582.1740587","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2010,5]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}