{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:56:34Z","timestamp":1725544594365},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540323013"},{"type":"electronic","value":"9783540322887"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11672142_33","type":"book-chapter","created":{"date-parts":[[2006,2,28]],"date-time":"2006-02-28T08:27:54Z","timestamp":1141115274000},"page":"408-419","source":"Crossref","is-referenced-by-count":3,"title":["Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets"],"prefix":"10.1007","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"33_CR1","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 Journal on Computing\u00a021(3), 521\u2013539 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"33_CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning. Machine Learning\u00a02(4), 319\u2013342 (1988)","journal-title":"Machine Learning"},{"key":"33_CR3","first-page":"1","volume-title":"Complexity Theory: Current Research","author":"V. Arvind","year":"1993","unstructured":"Arvind, V., Han, Y., Hemachandra, L., K\u00f6bler, J., Lozano, A., Mundhenk, M., Ogiwara, A., 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, Cambridge (1993)"},{"key":"33_CR4","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension in algorithmic information and computational complexity. SIAM Journal on Computing (to appear)"},{"issue":"2","key":"33_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM Journal on Computing\u00a06(2), 305\u2013322 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR6","first-page":"2","volume-title":"Proceedings of the 12th Annual IEEE Conference on Computational Complexity","author":"H. Buhrman","year":"1997","unstructured":"Buhrman, H., Fortnow, L., Torenvliet, L.: Six hypotheses in search of a theorem. In: Proceedings of the 12th Annual IEEE Conference on Computational Complexity, pp. 2\u201312. IEEE Computer Society, Los Alamitos (1997)"},{"key":"33_CR7","first-page":"307","volume-title":"Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science","author":"J. Cai","year":"1996","unstructured":"Cai, J., Naik, A.V., Sivakumar, D.: On the existence of hard sparse sets under weak reductions. In: Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, pp. 307\u2013318. Springer, Heidelberg (1996)"},{"issue":"5","key":"33_CR8","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.1137\/S0097539792237188","volume":"24","author":"B. Fu","year":"1995","unstructured":"Fu, B.: With quasilinear queries EXP is not polynomial time Turing reducible to sparse sets. SIAM Journal on Computing\u00a024(5), 1082\u20131090 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR9","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1109\/SCT.1992.215396","volume-title":"Proceedings of the Seventh Annual Structure in Complexity Theory Conference","author":"L.A. Hemachandra","year":"1992","unstructured":"Hemachandra, L.A., Ogiwara, M., Watanabe, O.: How hard are sparse sets? In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference, pp. 222\u2013238. IEEE Computer Society Press, Los Alamitos (1992)"},{"issue":"1","key":"33_CR10","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1016\/S0304-3975(01)00340-1","volume":"289","author":"J.M. Hitchcock","year":"2002","unstructured":"Hitchcock, J.M.: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science\u00a0289(1), 861\u2013869 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"33_CR11","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jcss.2003.09.001","volume":"69","author":"J.M. Hitchcock","year":"2004","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Scaled dimension and nonuniform complexity. Journal of Computer and System Sciences\u00a069(2), 97\u2013122 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"33_CR12","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/1086649.1086662","volume":"36","author":"J.M. Hitchcock","year":"2005","unstructured":"Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: The fractal geometry of complexity classes. SIGACT News\u00a036(3), 24\u201338 (2005)","journal-title":"SIGACT News"},{"issue":"1","key":"33_CR13","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/0890-5401(89)90029-1","volume":"81","author":"K. Ko","year":"1989","unstructured":"Ko, K.: Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Information and Computation\u00a081(1), 62\u201387 (1989)","journal-title":"Information and Computation"},{"issue":"2","key":"33_CR14","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s002249910010","volume":"33","author":"W. Lindner","year":"2000","unstructured":"Lindner, W., Schuler, R., Watanabe, O.: Resource-bounded measure and learnability. Theory of Computing Systems\u00a033(2), 151\u2013170 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"4","key":"33_CR15","first-page":"285","volume":"2","author":"N. Littlestone","year":"1987","unstructured":"Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning\u00a02(4), 285\u2013318 (1987)","journal-title":"Machine Learning"},{"issue":"2","key":"33_CR16","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. Journal of Computer and System Sciences\u00a044(2), 220\u2013258 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-1-4612-1872-2_10","volume-title":"Complexity Theory Retrospective II","author":"J.H. Lutz","year":"1997","unstructured":"Lutz, J.H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp. 225\u2013254. Springer, Heidelberg (1997)"},{"issue":"5","key":"33_CR18","doi-asserted-by":"publisher","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM Journal on Computing\u00a032(5), 1236\u20131259 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"33_CR19","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J.H. Lutz","year":"1994","unstructured":"Lutz, J.H., Mayordomo, E.: Measure, stochasticity, and the density of hard languages. SIAM Journal on Computing\u00a023(4), 762\u2013779 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR20","first-page":"64","volume":"68","author":"J.H. Lutz","year":"1999","unstructured":"Lutz, J.H., Mayordomo, E.: Twelve problems in resource-bounded measure. Bulletin of the European Association for Theoretical Computer Science\u00a068, 64\u201380 (1999); Also in Current Trends in Theoretical Computer Science: Entering the 21st Century, pp. 83\u2013101, World Scientific Publishing, Singapore (2001)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"issue":"4","key":"33_CR21","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1137\/S0097539797321547","volume":"30","author":"J.H. Lutz","year":"2000","unstructured":"Lutz, J.H., Zhao, Y.: The density of weakly complete problems under adaptive reductions. SIAM Journal on Computing\u00a030(4), 1197\u20131210 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR22","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 of Berman and Hartmanis. Journal of Computer and System Sciences\u00a025, 130\u2013143 (1982)","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR23","unstructured":"Mayordomo, E.: Personal communication (2002)"},{"key":"33_CR24","unstructured":"Meyer, A.R.: Reported in [5] (1977)"},{"issue":"3","key":"33_CR25","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/0220030","volume":"20","author":"M. Ogiwara","year":"1991","unstructured":"Ogiwara, M., Watanabe, O.: On polynomial bounded truth-table reducibility of NP sets to sparse sets. SIAM Journal on Computing\u00a020(3), 471\u2013483 (1991)","journal-title":"SIAM Journal on Computing"},{"key":"33_CR26","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1109\/PSCT.1987.10319263","volume-title":"Proceedings of the Second Structure in Complexity Theory Conference","author":"O. Watanabe","year":"1987","unstructured":"Watanabe, O.: Polynomial time reducibility to a set of small density. In: Proceedings of the Second Structure in Complexity Theory Conference, pp. 138\u2013146. IEEE Computer Society, Los Alamitos (1987)"}],"container-title":["Lecture Notes in Computer Science","STACS 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11672142_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,3]],"date-time":"2024-02-03T03:59:36Z","timestamp":1706932776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11672142_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540323013","9783540322887"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/11672142_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}