{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T02:30:01Z","timestamp":1775097001471,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540562870","type":"print"},{"value":"9783540475071","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56287-7_99","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:02:40Z","timestamp":1330254160000},"page":"116-127","source":"Crossref","is-referenced-by-count":23,"title":["Superpolynomial circuits, almost sparse oracles and the exponential hierarchy"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Steven","family":"Homer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Allender E. & O. Watanabe. Kolmogorov Complexity and Degrees of Tally Sets. Proc. Structure in Complexity Theory third annual conference, IEEE Computer Society Press (1988).","DOI":"10.1109\/SCT.1988.5269"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Babai L., L. Fortnow & C. Lund. Non-deterministic exponential time has twoprover interactive protocols. Proc. 31st IEEE Symp. on Foundations of Computer Science, (1990) pp16\u201325.","DOI":"10.1109\/FSCS.1990.89520"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0022-0000(90)90025-G","volume":"41","author":"J.L. Balc\u00e1zar","year":"1990","unstructured":"Balc\u00e1zar J.L. Self-reducibilityi. Journal of Computer and System Sciences 41 (1990) pp367\u2013388.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR4","unstructured":"Balc\u00e1zar J.L., J. D\u00edaz & J. Gabarr\u00f3. Structural Complexity I. W. Brauer, G. Rozenberg & A. Salomaa (eds.) EATCS Monographs on Theoretical Computer Science 11 (1988) Springer Verlag."},{"key":"8_CR5","unstructured":"Feige U., S. Goldwasser, L. Lov\u00e1sz, S. Safra & M. Szegedy Approximating Clique is Almost NP-complete. Manuscript."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/S0019-9958(85)80004-8","volume":"65","author":"J. Hartmanis","year":"1985","unstructured":"Hartmanis J., N. Immerman & V. Sewelson. Sparse Set in NP-P: EXPTIME versus NEXPTIME. Information and Control, 65 (1985) pp158\u2013181.","journal-title":"Information and Control"},{"key":"8_CR7","unstructured":"Hemachandra L.A. Counting in Structural Complexity Theory. Ph.D. thesis Cornell University (1987)."},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Homer S. & L. Longpr\u00e9. On Reductions of NP Sets to Sparse Sets. To appear in Proc. Structure in Complexity Theory sixth annual conference (1991) in Chigaco Il.","DOI":"10.1109\/SCT.1991.160246"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Kadin J. PNP[logn] and sparse Turing complete sets for NP. Proc. Structure in Complexity Theory second annual conference, IEEE Computer Society Press (1987) pp33\u201340.","DOI":"10.1109\/PSCT.1987.10319252"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(82)90382-5","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan R. Circuit-size Lower Bounds and Non-reducibility to Sparse Sets. Information and Control 55 (1982) pp40\u201346.","journal-title":"Information and Control"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Karp, R.M. Reducibility among combinatorial problems. Complexity of Computer Computations, R.E. Miller & J.W. Thatcher eds. Plenum N.Y. pp85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.M. & R.J. Lipton. Some connections between nonuniform and uniform complexity classes. Proc. 21 st IEEE Found. Comput. Sci. (1980) pp302\u2013309.","DOI":"10.1145\/800141.804678"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S.R. Mahaney","year":"1982","unstructured":"Mahaney S.R. Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis. Journal of Computer and System Sciences 25 (1982) pp130\u2013143.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR14","unstructured":"Ogiwara M. & A. Lozano. On One Word-Decreasing Self-Reducible Sets. To appear in Proc. Sructure in Complexity Theory sixth annual conference (1991) in Chigaco Il."},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Ogiware M. & O. Watanabe On polynomial time boounded truth-table reducibility of NP sets to sparse sets. Proc. 22nd Annual ACM Symposium on Theory of Computing (1990) pp457\u2013467.","DOI":"10.1145\/100216.100276"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0022-0000(85)90040-6","volume":"31","author":"C.B. Wilson","year":"1985","unstructured":"Wilson, C.B. Relativized Circuit Complexity J. Comp. Sys. Sci. 31 (1985) pp169\u2013181.","journal-title":"J. Comp. Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56287-7_99.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:47:21Z","timestamp":1742593641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56287-7_99"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562870","9783540475071"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-56287-7_99","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}