{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T13:42:50Z","timestamp":1730295770584,"version":"3.28.0"},"reference-count":22,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2002.1181982","type":"proceedings-article","created":{"date-parts":[[2003,6,26]],"date-time":"2003-06-26T15:35:00Z","timestamp":1056641700000},"page":"583-592","source":"Crossref","is-referenced-by-count":1,"title":["Bounded-depth Frege lower bounds for weaker pigeonhole principles"],"prefix":"10.1109","author":[{"given":"J.","family":"Buresh-Oppenheim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Beame","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Raz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Sabharwal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"19","first-page":"100","article-title":"Proof complexity of pigeonhole principles","author":"razborov","year":"2001","journal-title":"Proceedings of the Fifth International Conference on Developments in Language Theory"},{"key":"22","first-page":"253","article-title":"Reducibility by algebraic projections","volume":"28","author":"valiant","year":"1982","journal-title":"L'Enseignement Mathe?matique"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509987"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"15","first-page":"317","article-title":"Counting problems in bounded arithmetic","author":"paris","year":"1985","journal-title":"Methods in Mathematical Logic Proceedings of the 6th Latin American Symposium on Mathematical Logic 1983 Volume 1130 of Lecture Notes in Mathematics"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.2307\/2274618"},{"journal-title":"Bounded arithmetic propositional logic and complexity theory","year":"1996","author":"kraji?c?ek","key":"13"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335348"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959894"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1040046140"},{"article-title":"A switching lemma primer","year":"1994","author":"beame","key":"3"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004336"},{"key":"2","first-page":"1005","article-title":"Lower bounds for the weak pigeonhole principle beyond resolution","author":"atserias","year":"2001","journal-title":"Automata Languages and Programming 28th International Colloquium Volume 2076 of Lecture Notes in Computer Science"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01302964"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766251"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004323"},{"key":"5","first-page":"13","article-title":"More on the relative strength of counting principles","author":"beame","year":"1998","journal-title":"Proof Complexity and Feasible Arithmetics Volume 39 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129733"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.2307\/2273826"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90072-2"}],"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\/01181982.pdf?arnumber=1181982","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,14]],"date-time":"2017-03-14T00:06:43Z","timestamp":1489450003000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1181982\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":22,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2002.1181982","relation":{},"subject":[]}}