{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:23Z","timestamp":1742598623240,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_109","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:57Z","timestamp":1330275597000},"page":"609-618","source":"Crossref","is-referenced-by-count":2,"title":["On the sparse set conjecture for sets with low density"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Montserrat","family":"Hermo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"53_CR1","doi-asserted-by":"crossref","unstructured":"V. Arvind, Y. Han, L. Hemachandra, J. Koebler, A. Lozano, M. Mundhenk, M. Ogiwara, U. Sch\u00f6ning, R. Silvestri, and T. Thierauf. Reductions to sets of low information content. In K. Ambos-Spies, S. Homer, and U. Sch\u00f6ning, editors, Complexity Theory, pages 1\u201346. Cambridge University Press, December 1993.","DOI":"10.1007\/3-540-55719-9_72"},{"key":"53_CR2","doi-asserted-by":"crossref","unstructured":"R. Beigel, M. Bellare, J. Feigenbaum, and S. Goldwasser. Languages that are easier to verify than their proofs. In Proc. 32nd IEEE Symposium on Foundations of Computer Science, pages 19\u201328, 1991.","DOI":"10.1109\/SFCS.1991.185343"},{"key":"53_CR3","volume-title":"Technical Report TR76-284","author":"A. Borodin","year":"1976","unstructured":"A. Borodin and A. Deniers. Some comments on functional self-reducibility and the NP hierarchy. Technical Report TR76-284, Cornell University, Department of Computer Science, Upson Hall, Ithaca, NY 14853, 1976."},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Springer-Verlag, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"53_CR5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and H. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM J. Comput., 6:305\u2013322, 1977.","journal-title":"SIAM J. Comput."},{"key":"53_CR6","doi-asserted-by":"crossref","unstructured":"H. Buhrman and S. Homer. Superpolynomial circuits, almost sparse oracles and the exponential hierarchy. In R. Shyamasundar, editor, Proc. 12th Conference on the Foundations of Software Technology & Theoretical Computerscience, Lecture Notes in Computer Science, pages 116\u2013127. Springer Verlag, 1992.","DOI":"10.1007\/3-540-56287-7_99"},{"key":"53_CR7","unstructured":"J.L. Balc\u00e1zar, M. Hermo, and E. Mayordomo. Characterizations of logarithmic advice complexity classes. In Algorithms, Software, Architecture: Information Procesing 92, volume 1, pages 315\u2013321. Elsevier, 1992."},{"key":"53_CR8","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":"53_CR9","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/S0022-0000(05)80006-6","volume":"48","author":"S. Homer","year":"1994","unstructured":"S. Homer and L. Longpr\u00e9. On reductions of NP sets to sparse sets. J. Computer and System Sciences, 48:324\u2013336, 1994.","journal-title":"J. Computer and System Sciences"},{"key":"53_CR10","doi-asserted-by":"crossref","unstructured":"L. Hemaspaandra, M. Ogiwara, and S. Toda. Space-efficient recognition of sparse self-reducible languages. Computational Complexity. In press.","DOI":"10.1007\/BF01206639"},{"issue":"1\u20133","key":"53_CR11","doi-asserted-by":"crossref","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(1\u20133):40\u201356, October\/November\/December 1982.","journal-title":"Information and Control"},{"issue":"1","key":"53_CR12","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1137\/0209003","volume":"9","author":"C. Kintala","year":"1980","unstructured":"C. Kintala and P. Fisher. Refining nondeterminism in relativized polynomial-time bounded computations. SIAM J. Comput., 9(1):46\u201353, 1980.","journal-title":"SIAM J. Comput."},{"key":"53_CR13","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":"53_CR14","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0304-3975(87)90078-8","volume":"52","author":"K. Ko","year":"1987","unstructured":"K. Ko. On helping by robust oracle machines that take advice. Theoretical Computer Science, 52:15\u201336, 1987.","journal-title":"Theoretical Computer Science"},{"key":"53_CR15","first-page":"52","volume-title":"P-selective sets, and reducing search to decision vs. self-reducibility","author":"A.V. Naik","year":"1993","unstructured":"A.V. Naik, M. Ogiwara, and A.L. Selman. P-selective sets, and reducing search to decision vs. self-reducibility. In Proc. Structure in Complexity Theory 8th annual conference, pages 52\u201364, San Diego, California, 1993. IEEE computer society press."},{"key":"53_CR16","first-page":"139","volume-title":"On one query self-reducible sets","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and A. Lozano. On one query self-reducible sets. In Proc. Structure in Complexity Theory 6th annual conference, pages 139\u2013151, Chicago, Ill., 1991. IEEE Computer Society Press."},{"key":"53_CR17","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"M. Ogiwara and O. Watanabe. On polynomial time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput., 20:471\u2013483, 1991.","journal-title":"SIAM J. Comput."},{"key":"53_CR18","doi-asserted-by":"crossref","unstructured":"N. Pippenger. On simultaneous resource bounds. In Proc. 20th IEEE Symposium on Foundations of Computer Science, pages 307\u2013311, 1979.","DOI":"10.1109\/SFCS.1979.29"},{"key":"53_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. J. Comput. System Sci., 31:169\u2013181, 1985.","journal-title":"J. Comput. System Sci."}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_109.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:42:13Z","timestamp":1742596933000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_109"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_109","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}