{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T19:14:22Z","timestamp":1793128462624,"version":"4.5.0"},"reference-count":14,"publisher":"IEEE Comput. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/ccc.2003.1214433","type":"proceedings-article","created":{"date-parts":[[2004,1,23]],"date-time":"2004-01-23T23:33:03Z","timestamp":1074900783000},"page":"347-350","source":"Crossref","is-referenced-by-count":5,"title":["Proving SAT does not have small circuits with an application to the two queries problem"],"prefix":"10.1109","author":[{"given":"L.","family":"Fortnow","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Sengupta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"13","article-title":"Number-of-query hierarchies","volume":"158","author":"wagner","year":"1987","journal-title":"Technical Report"},{"key":"14","article-title":"Number-of-query hierarchies","volume":"4","author":"wagner","year":"1989","journal-title":"Technical Report"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00146-8"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050007"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1647"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0032"},{"key":"1","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF01371729","article-title":"A relationship between difference hierarchies and relativized polynomial hierarchies","volume":"26","author":"beigel","year":"1993","journal-title":"Mathematical Systems Theory"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891"},{"key":"6","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1137\/S0097539790178069","article-title":"The boolean hierarchy and the polynomial hierarchy; A closer connection","volume":"25","author":"chang","year":"1996","journal-title":"SIAM Journal on Computing"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00016-6"},{"key":"4","first-page":"620","author":"cai","year":"2001","journal-title":"Proceedings of the 42nd IEEE Conference on Foundations of Computer Science (FOCS)"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1137\/0217080"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"}],"event":{"name":"18th IEEE Annual Conference on Computational Complexity","location":"Aarhus, Denmark","acronym":"CCC-03"},"container-title":["18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8614\/27296\/01214433.pdf?arnumber=1214433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,15]],"date-time":"2017-06-15T23:18:21Z","timestamp":1497568701000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1214433\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":14,"URL":"https:\/\/doi.org\/10.1109\/ccc.2003.1214433","relation":{},"subject":[]}}