{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T08:45:27Z","timestamp":1773996327924,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662006","type":"print"},{"value":"9783540486862","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48686-0_21","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:12Z","timestamp":1184586852000},"page":"210-220","source":"Crossref","is-referenced-by-count":19,"title":["Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy"],"prefix":"10.1007","author":[{"given":"Peter Bro","family":"Miltersen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Osamu","family":"Watanabe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,25]]},"reference":[{"key":"21_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BFb0058034","volume-title":"Proceedings of the 17th conference on the Foundations of Software Technology and Theoretical Computer Science","author":"V. Arvind","year":"1997","unstructured":"V. Arvind and J. K\u00f6bler. On resource-bounded measure and pseudorandomness. Proceedings of the 17th conference on the Foundations of Software Technology and Theoretical Computer Science, LNCS Vol. 1346, (1997), pp. 235\u2013249."},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, L. Levin and M. Szegedy. Checking computations in polylogarithmic time. Procedings of the 23rd ACM Symposium on the Theory of Computation, (1991), pp. 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L. Babai","year":"1990","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity, 1, (1990), pp. 3\u201340.","journal-title":"Computational Complexity"},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan and A. Wigdersen. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3, (1993), pp. 307\u2013318.","journal-title":"Computational Complexity"},{"key":"21_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity \u2014 I & II","author":"J. L. Balc\u00e1zar","year":"1988","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz and J. Gabarr\u00f3. Structural Complexity \u2014 I & II. Springer Verlag, Berlin Heidelberg, 1988."},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N.H. Bshouty","year":"1996","unstructured":"N.H. Bshouty, R. Cleve, R. Gavalda, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52, (1996), pp. 421\u2013433.","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"H. Buhrman, L. Fortnow and T. Thierauf. Nonrelativizing separations. Proceedings of the 13th IEEE conference on Computational Complexity, (1998), pp. 8\u201312.","DOI":"10.1109\/CCC.1998.694585"},{"key":"21_CR8","unstructured":"O. Goldreich and D. Zuckerman. Another proof that BPP \u2286 PH (and more). ECCC TR97-045, (1997). Available at http:\/\/www.eccc.uni-trier.de\/eccc\/ ."},{"key":"21_CR9","volume-title":"Cambridge Tracts in Mathematics and Mathematical Physics","author":"G.H. Hardy","year":"1924","unstructured":"G.H. Hardy. Orders of Infinity. Cambridge Tracts in Mathematics and Mathematical Physics, No. 12. Second edition. Cambridge University Press, Cambridge, 1924.","edition":"Second edition"},{"key":"21_CR10","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, (1982), pp. 40\u201356.","journal-title":"Information and Control"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. Proceedings of the 12th ACM Symposium on Theory of Computing, (1980), pp. 302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"21_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/3-540-60084-1_74","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming","author":"J. K\u00f6bler","year":"1995","unstructured":"J. K\u00f6bler and O. Watanabe. New collapse consequences of NP having small circuits. Proceedings of the International Colloquium on Automata, Languages and Programming, LNCS Vol. 944, (1995), pp. 196\u2013207."},{"key":"21_CR13","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1017\/S1446788700026914","volume":"2","author":"K.W. Morris","year":"1962","unstructured":"K.W. Morris and G. Szekeres. Tables of the logarithm of iteration of e x - 1. J. Australian Math. Soc. 2, (1962), pp. 321\u2013327.","journal-title":"J. Australian Math. Soc."},{"key":"21_CR14","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994."},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"P. B. Miltersen, N. V. Vinodchandran and O. Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. Research Report c-130, Dept. of Math. and Comput. Sc., Tokyo Inst. of Tech. Available at http:\/\/www.is.titech.ac.jp\/research\/research-report\/C\/ , 1999.","DOI":"10.1007\/3-540-48686-0_21"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1017\/S1446788700026902","volume":"2","author":"G. Szekeres","year":"1962","unstructured":"G. Szekeres. Fractional iteration of exponentially growing functions. J. Australian Math. Soc. 2, (1962), 301\u2013320.","journal-title":"J. Australian Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48686-0_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:13:09Z","timestamp":1556665989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48686-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662006","9783540486862"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-48686-0_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}