{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,22]],"date-time":"2024-10-22T21:18:15Z","timestamp":1729631895049,"version":"3.28.0"},"reference-count":32,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181984","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T15:35:00Z","timestamp":1056641700000},"page":"604-613","source":"Crossref","is-referenced-by-count":4,"title":["Switching lemma for small restrictions and lower bounds for k-DNF resolution"],"prefix":"10.1109","author":[{"given":"N.","family":"Segerlind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Buss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Impagliazzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"},{"key":"ref31","article-title":"On the complexity of proofs in propositionallogics","volume":"8","author":"tseitin","year":"1970","journal-title":"Seminars in Mathematics"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808733"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814614"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90072-2"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795282432"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/48014.48016"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.2307\/2273702"},{"key":"ref16","article-title":"Tree resolution proofs of the weak pigeon-hole principle","author":"dantchev","year":"2001","journal-title":"Ninth Annual Structure in Complexity Theory Conference"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_20"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029622"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509987"},{"key":"ref4","article-title":"A switching lemma primer","author":"beame","year":"1994","journal-title":"Technical Report"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1016\/S0049-237X(98)80023-2","article-title":"The lengths of proofs","author":"pudl\u00e1k","year":"1998","journal-title":"Handbook of Proof Theory"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_81"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548486"},{"key":"ref29","article-title":"Improved resolution lower bounds for the weak pigeonhole principle","author":"razborov","year":"2001","journal-title":"Electronic Colloquium on Computational Complexity Technical Reports"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276870"},{"key":"ref8","doi-asserted-by":"crossref","DOI":"10.1145\/509907.509988","article-title":"Hard examples for bounded depth frege","author":"ben-sasson","year":"2002","journal-title":"ACM Symposium on Theory of Computing (STOC)"},{"key":"ref7","first-page":"66","article-title":"Propositional proof complexity: Past, present, and future","volume":"65","author":"beame","year":"1998","journal-title":"Bulletin of the EATCS"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45793-3_38"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"ref22","article-title":"Almost optimal lower bounds for small depth circuits","volume":"5","author":"h\u00e5stad","year":"1989","journal-title":"ADVCR Advances in Computing Research"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"article-title":"Bounded Arithmetic, Propositional Logic and Complexity Theory","year":"1995","author":"kraj\u00edek","key":"ref23"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380821"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335348"}],"event":{"name":"43rd Annual IEEE Symposium on Foundations of Computer Science","acronym":"SFCS-02","location":"Vancouver, BC, Canada"},"container-title":["The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8411\/26517\/01181984.pdf?arnumber=1181984","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,10]],"date-time":"2024-01-10T05:02:20Z","timestamp":1704862940000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181984\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":32,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181984","relation":{},"subject":[]}}