{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:40:26Z","timestamp":1737502826999,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_22","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"202-211","source":"Crossref","is-referenced-by-count":3,"title":["On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"issue":"3","key":"22_CR1","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"N. Bshouty, R. Cleve, R. Gavald\u00e0, S. Kannan, and C. Tamon, Oracles and queries that are sufficient for exact learning, J. Comput. and System Sci. 52(3), 421\u2013433, 1996.","journal-title":"J. Comput. and System Sci."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"H. Buhrman, L. Fortnow, and T. Thierauf, Nonrelativizing separations, in Proc. the 13th IEEE Conference on Computational Complexity (CCC\u201998), IEEE, 8\u201312, 1998.","DOI":"10.1109\/CCC.1998.694585"},{"issue":"1","key":"22_CR3","first-page":"21","volume":"38","author":"J-Y. Cai","year":"1986","unstructured":"J-Y. Cai, With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, in Proc. 18th ACM Symposium on Theory of Computing (STOC\u201986), ACM, 21\u201329, 1986. See also the journal version appeared in J. Comput. and System Sci. 38(1): 68\u201385 (1989).","journal-title":"J. Comput. and System Sci"},{"key":"22_CR4","unstructured":"J-Y. Cai, S 2 \u03a1 P 2 ZPPN\u03a1, in Proc. 42th IEEE Symposium on Foundations of Computer Science (FOCS\u201901), IEEE, 620\u2013628, 2001."},{"key":"22_CR5","unstructured":"J-Y. Cai and O. Watanabe, Research Report C-167, Dept. of Math. Comput. Sci., Tokyo Inst. of Tech., 2003. Available from www.is.titech.ac.jp\/research\/research-report\/C\/index.html."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Saxe, and M. Sipser, Parity, circuits, and the polynomial time hierarchy, in Proc. 22nd IEEE Symposium on Foundations of Computer Science (FOCS\u201981), IEEE, 260\u2013270, 1981.","DOI":"10.1109\/SFCS.1981.35"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Almost optimal lower bounds for small depth circuits, in Proc. 18th ACM Symposium on Theory of Computing (STOC\u201986), ACM, 6\u201320, 1986.","DOI":"10.1145\/12130.12132"},{"issue":"4","key":"22_CR8","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1137\/0213045","volume":"13","author":"H. Heller","year":"1984","unstructured":"H. Heller, On relativized polynomial and exponential computations, SIAM J. Comput. 13(4), 717\u2013725, 1984.","journal-title":"SIAM J. Comput."},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"R. Kannan, Circuit-size lower bounds and non-reducibility to sparse sets, Information and Control, 55, 40\u201356, 1982.","journal-title":"Information and Control"},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"R.M. Karp and R.J. Lipton, Some connections between nonuniform and uniform complexity classes, in Proc. 12th ACM Symposium on Theory of Computing (STOC\u201980), ACM, 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1137\/S0097539795296206","volume":"28","author":"J. K\u00f6bler","year":"1998","unstructured":"J. K\u00f6bler and O. Watanabe, New collapse consequences of NP having small circuits, SIAM J. Comput., 28, 311\u2013324, 1998.","journal-title":"SIAM J. Comput."},{"key":"22_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/3-540-48686-0_21","volume-title":"Proc. 5th Annual International Conference on Computing and Combinatorics (COCOON\u201999)","author":"P.B. Miltersen","year":"1999","unstructured":"P.B. Miltersen, N.V. Vinodchandran, and O. Watanabe, Super-Polynomial versus half-exponential circuit size in the exponential hierarchy, in Proc. 5th Annual International Conference on Computing and Combinatorics (COCOON\u201999), Lecture Notes in Computer Science 1627, 210\u2013220, 1999."},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"N. Nisan and A. Wigderson, Hardness vs randomness, J. Comput. Syst. Sci. 49, 149\u2013167, 1994.","journal-title":"J. Comput. Syst. Sci."},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"J. van Lint, Introduction to Coding Theory, Springer-Verlag, 1991.","DOI":"10.1007\/978-3-662-00174-5"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:25:42Z","timestamp":1737501942000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}