{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:42:40Z","timestamp":1725745360371},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403125"},{"type":"electronic","value":"9783642403132"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40313-2_23","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T10:36:43Z","timestamp":1376649403000},"page":"243-253","source":"Crossref","is-referenced-by-count":1,"title":["Learning Reductions to Sparse Sets"],"prefix":"10.1007","author":[{"given":"Harry","family":"Buhrman","sequence":"first","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]},{"given":"John M.","family":"Hitchcock","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Loff","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"23_CR1","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0304-3975(95)00073-9","volume":"158","author":"M. Agrawal","year":"1996","unstructured":"Agrawal, M., Arvind, V.: Geometric sets of low information content. Theor. Comput. Sci.\u00a0158(1-2), 193\u2013219 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"23_CR2","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1137\/0221034","volume":"21","author":"E. Allender","year":"1992","unstructured":"Allender, E., Hemachandra, L.A., Ogiwara, M., Watanabe, O.: Relating equivalence and reducibility to sparse sets. SIAM J. Comput.\u00a021(3), 521\u2013539 (1992)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"23_CR3","first-page":"319","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Queries and concept learning. Mach. Learn.\u00a02(4), 319\u2013342 (1987)","journal-title":"Mach. Learn."},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Arvind, V., Han, Y., Hemachandra, L., K\u00f6bler, J., Lozano, A., Mundhenk, M., Ogiwara, M., Sch\u00f6ning, U., Silvestri, R., Thierauf, T.: Reductions to sets of low information content. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory: Current Research, pp. 1\u201345. Cambridge University Press (1993)","DOI":"10.1007\/3-540-55719-9_72"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Arvind, V., K\u00f6bler, J., Mundhenk, M.: Bounded truth-table and conjunctive reductions to sparse and tally sets. Technical report, University of Ulm (1992)","DOI":"10.1007\/3-540-56287-7_101"},{"key":"23_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/3-540-56279-6_78","volume-title":"Algorithms and Computation","author":"V. Arvind","year":"1992","unstructured":"Arvind, V., K\u00f6bler, J., Mundhenk, M.: Lowness and the complexity of sparse and tally descriptions. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol.\u00a0650, pp. 249\u2013258. Springer, Heidelberg (1992)"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Arvind, V., K\u00f6bler, J., Mundhenk, M.: On bounded truth-table, conjunctive, and randomized reductions to sparse sets. In: Proc. 12th CFSTTCS, pp. 140\u2013151. Springer (1992)","DOI":"10.1007\/3-540-56287-7_101"},{"key":"23_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/3-540-57182-5_15","volume-title":"Mathematical Foundations of Computer Science 1993","author":"V. Arvind","year":"1993","unstructured":"Arvind, V., K\u00f6bler, J., Mundhenk, M.: Hausdorff reductions to sparse sets and to sets of high information content. In: Borzyszkowski, A.M., Sokolowski, S. (eds.) MFCS 1993. LNCS, vol.\u00a0711, pp. 232\u2013241. Springer, Heidelberg (1993)"},{"issue":"2","key":"23_CR10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1051\/ita\/1996300201551","volume":"30","author":"V. Arvind","year":"1996","unstructured":"Arvind, V., K\u00f6bler, J., Mundhenk, M.: Monotonous and randomized reductions to sparse sets. Theo. Inform. and Appl.\u00a030(2), 155\u2013179 (1996)","journal-title":"Theo. Inform. and Appl."},{"key":"23_CR11","first-page":"63","volume":"29","author":"V. Arvind","year":"1996","unstructured":"Arvind, V., K\u00f6bler, J., Mundhenk, M.: Upper bounds for the complexity of sparse and tally descriptions. Theor. Comput. Syst.\u00a029, 63\u201394 (1996)","journal-title":"Theor. Comput. Syst."},{"key":"23_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/3-540-49116-3_26","volume-title":"STACS 99","author":"V. Arvind","year":"1999","unstructured":"Arvind, V., Tor\u00e1n, J.: Sparse sets, approximable sets, and parallel queries to NP. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 281\u2013290. Springer, Heidelberg (1999)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Berman, L., Hartmanis, J.: On isomorphisms and density of NP and other complete sets. In: Proc. 8th STOC, pp. 30\u201340 (1976)","DOI":"10.1145\/800113.803628"},{"issue":"3","key":"23_CR14","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N.H. Bshouty","year":"1996","unstructured":"Bshouty, N.H., Cleve, R., Gavald\u00e0, R., Kannan, S., Tamon, C.: Oracles and queries that are sufficient for exact learning. J. Comput. Syst. Sci.\u00a052(3), 421\u2013433 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"23_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jcss.2003.07.015","volume":"73","author":"J.-Y. Cai","year":"2002","unstructured":"Cai, J.-Y.: S\n                  \n                    \n                  \n                  $^{p}_{2}$\n                 \u2286 ZPPNP. J. Comput. Syst. Sci.\u00a073(1), 25\u201335 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-60922-9_26","volume-title":"STACS 96","author":"J.-Y. Cai","year":"1996","unstructured":"Cai, J.-Y., Naik, A.V., Sivakumar, D.: On the existence of hard sparse sets under weak reductions. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol.\u00a01046, pp. 307\u2013318. Springer, Heidelberg (1996)"},{"key":"23_CR17","unstructured":"Fortnow, L., Klivans, A.: NP with small advice. In: Proc. 20th CCC, pp. 228\u2013234 (2005)"},{"issue":"3","key":"23_CR18","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s00224-010-9288-1","volume":"49","author":"R. Harkins","year":"2011","unstructured":"Harkins, R., Hitchcock, J.M.: Dimension, halfspaces, and the density of hard sets. Theor. Comput. Syst.\u00a049(3), 601\u2013614 (2011)","journal-title":"Theor. Comput. Syst."},{"issue":"6","key":"23_CR19","doi-asserted-by":"publisher","first-page":"1696","DOI":"10.1137\/050647517","volume":"36","author":"J.M. Hitchcock","year":"2007","unstructured":"Hitchcock, J.M.: Online learning and resource-bounded dimension: Winnow yields new lower bounds for hard sets. SIAM J. Comput.\u00a036(6), 1696\u20131708 (2007)","journal-title":"SIAM J. Comput."},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits. In: Proc. 29th STOCS, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"3","key":"23_CR21","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/0022-0000(89)90024-X","volume":"39","author":"J. Kadin","year":"1989","unstructured":"Kadin, J.: P\n                        NP[O(logn)] and sparse Turing-complete sets for NP. J. Comput. Syst. Sci.\u00a039(3), 282\u2013298 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1-3","key":"23_CR22","first-page":"40","volume":"55","author":"R. Kannan","year":"1982","unstructured":"Kannan, R.: Circuit-size lower bounds and non-reducibility to sparse sets. Inform. Comput.\u00a055(1-3), 40\u201356 (1982)","journal-title":"Inform. Comput."},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R., Lipton, R.: Some connections between nonuniform and uniform complexity classes. In: Proc. 12th STOC, pp. 302\u2013309 (1980)","DOI":"10.1145\/800141.804678"},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-60084-1_74","volume-title":"Automata, Languages and Programming","author":"J. K\u00f6bler","year":"1995","unstructured":"K\u00f6bler, J., Watanabe, O.: New collapse consequences of NP having small circuits. In: F\u00fcl\u00f6p, Z., G\u00e9cseg, F. (eds.) ICALP 1995. LNCS, vol.\u00a0944, pp. 196\u2013207. Springer, Heidelberg (1995)"},{"key":"23_CR25","first-page":"381","volume-title":"Worksh. Comput. Learn. Theor. & Natur. Learn. Syst.","author":"W. Maass","year":"1994","unstructured":"Maass, W., Tur\u00e1n, G.: How fast can a threshold gate learn? In: Worksh. Comput. Learn. Theor. & Natur. Learn. Syst., vol.\u00a01, pp. 381\u2013414. MIT Press, Cambridge (1994)"},{"issue":"2","key":"23_CR26","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"S. Mahaney","year":"1982","unstructured":"Mahaney, S.: Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis. J. Comput. Syst. Sci.\u00a025(2), 130\u2013143 (1982)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"23_CR27","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/0016-0032(61)90702-5","volume":"271","author":"S. Muroga","year":"1961","unstructured":"Muroga, S., Toda, I., Takasu, S.: Theory of majority decision elements. J. Franklin. I.\u00a0271(5), 376\u2013418 (1961)","journal-title":"J. Franklin. I."},{"issue":"2","key":"23_CR28","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci.\u00a049(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"23_CR29","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"Ogiwara, M., Watanabe, O.: Polynomial-time bounded truth-table reducibility of NP sets to sparse sets. SIAM J. Comput.\u00a020(3), 471\u2013483 (1991)","journal-title":"SIAM J. Comput."},{"key":"23_CR30","unstructured":"Ranjan, D., Rohatgi, P.: On randomized reductions to sparse sets. In: Proc. 7th STOC, pp. 239\u2013242 (1992)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40313-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T22:12:21Z","timestamp":1558303941000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40313-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403125","9783642403132"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40313-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}