{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:02Z","timestamp":1742617202292,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602460"},{"type":"electronic","value":"9783540447689"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60246-1_122","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:55:30Z","timestamp":1330278930000},"page":"159-168","source":"Crossref","is-referenced-by-count":5,"title":["Nonuniform lower bounds for exponential time classes"],"prefix":"10.1007","author":[{"given":"Steven","family":"Homer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarah","family":"Mocas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity, volume I","author":"J. Balc\u00e1zar","year":"1988","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity, volume I. Springer-Verlag, New York, 1988."},{"key":"14_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-75357-2","volume-title":"Structural Complexity, volume II","author":"J. Balc\u00e1zar","year":"1990","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity, volume II. Springer-Verlag, New York, 1990."},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. In Proc. 6th IEEE Structure in Complexity Theory, pages 213\u2013219, 1991.","DOI":"10.1109\/SCT.1991.160263"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"H. Buhrman and S. Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In Proc. of the Conf. on Foundations of Software Technology and Theoretical Computer Science, 1992.","DOI":"10.1007\/3-540-56287-7_99"},{"key":"14_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF02090764","volume":"23","author":"J. D\u00edaz","year":"1990","unstructured":"J. D\u00edaz and J. Tor\u00e1n. Classes of bounded nondeterminism. Math. Systems Theory, 23:21\u201332, 1990.","journal-title":"Math. Systems Theory"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"B. Fu. With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets. In Proc. IEEE Structure in Complexity Theory, pages 185\u2013191, 1993.","DOI":"10.1109\/SCT.1993.336528"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"R. Gavald\u00e0 and O. Watanabe. On the computational complexity of small descriptions. In Proc. 6th IEEE Structure in Complexity Theory, pages 89\u2013101, 1991.","DOI":"10.1109\/SCT.1991.160247"},{"key":"14_CR8","unstructured":"L. Hemachandra. Counting in structural complexity theory. Ph.D. Thesis, Cornell University, 1987."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proc.24th Annual FOCS Conference, pages 439\u2013445, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"14_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:40\u201346, 1982.","journal-title":"Information and Control"},{"key":"14_CR11","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C. M. R. Kintala","year":"1980","unstructured":"C. M. R. Kintala and P. C. Fischer. Refining nondeterminism in relativized polynomial-time bounded computations. SIAM Journal on Computing, 9:46\u201353, 1980.","journal-title":"SIAM Journal on Computing"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th ACM Symposium on Theory of Computing, pages 302\u2013309, 1980.","DOI":"10.1145\/800141.804678"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences, pages 220\u2013258, 1992.","DOI":"10.1016\/0022-0000(92)90020-J"},{"key":"14_CR14","unstructured":"J. H. Lutz. One-way functions and balanced NP. Unpublished manuscript."},{"key":"14_CR15","unstructured":"J. H. Lutz and E. Mayordomo. Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing, to appear."},{"key":"14_CR16","unstructured":"S. E. Mocas. Separating exponential time classes from polynomial time classes. Ph.D. Thesis, Northeastern University, 1993."},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the v-c dimension. In Proc. 8th IEEE Structure in Complexity Theory, pages 12\u201318, 1993.","DOI":"10.1109\/SCT.1993.336545"},{"key":"14_CR18","volume-title":"volume 211 of Lecture Notes in Computer Science","author":"U. Sch\u00f6ning","year":"1985","unstructured":"U. Sch\u00f6ning. Complexity and Structure, volume 211 of Lecture Notes in Computer Science. Springer-Verlag, New York, 1985."},{"key":"14_CR19","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C. B. Wilson","year":"1985","unstructured":"C. B. Wilson. Relativized circuit complexity. Journal Computer Systems Sci., 31:169\u2013181, 1985.","journal-title":"Journal Computer Systems Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1995"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60246-1_122.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:56:14Z","timestamp":1742597774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60246-1_122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602460","9783540447689"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-60246-1_122","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}