{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:56Z","timestamp":1787340236110,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2007,1]]},"abstract":"<jats:p>We establish a relationship between the online mistake\u2010bound model of learning and resource\u2010bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu [SIAM J. Comput., 24 (1995), pp. 1082\u20131090] and Lutz and Zhao [SIAM J. Comput., 30 (2000), pp. 1197\u20131210], and solves one of Lutz and Mayordomo\u2019s \u201ctwelve problems in resource\u2010bounded measure\u201d [Bull. Eur. Assoc. Theor. Comput. Sci. EATSC, 68 (1999), pp. 64\u201380].<\/jats:p>","DOI":"10.1137\/050647517","type":"journal-article","created":{"date-parts":[[2007,3,20]],"date-time":"2007-03-20T08:58:42Z","timestamp":1174381122000},"page":"1696-1708","source":"Crossref","is-referenced-by-count":9,"title":["Online Learning and Resource\u2010Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets"],"prefix":"10.1137","volume":"36","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,3,19]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0221034"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116828"},{"key":"R3","unstructured":"V. Arvind, Y. Han, L. Hemachandra, J. K\u00f6bler, A. Lozano, M. Mundhenk, A. Ogiwara, U. Sch\u00f6ning, R. Silvestri, and T. Thierauf,\n                      Reductions to sets of low information content\n                      , in Complexity Theory: Current Research, K. Ambos\u2010Spies, S. Homer, and U. Sch\u00f6ning, eds., Cambridge University Press, Cambridge, UK, 1993, pp. 1\u201345."},{"key":"R4","unstructured":"K. B. Athreya, J. M. Hitchcock, J. H. Lutz, and E. Mayordomo,\n                      Effective strong dimension in algorithmic information and computational complexity\n                      , in Proceedings of the 21st Annual Symposium on Theoretical Aspects of Computer Science, Springer, Berlin, 2004, pp. 632\u2013643."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"R6","unstructured":"H. Buhrman, L. Fortnow, and L. Torenvliet,\n                      Six hypotheses in search of a theorem\n                      , in Proceedings of the 12th Annual IEEE Conference on Computational Complexity, IEEE Computer Society, Piscataway, NJ, 1997, pp. 2\u201312."},{"key":"R7","unstructured":"J. Cai, A. V. Naik, and D. Sivakumar,\n                      On the existence of hard sparse sets under weak reductions\n                      , in Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, Springer, Berlin, 1996, pp. 307\u2013318."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792237188"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.02.022"},{"key":"R10","unstructured":"L. A. Hemachandra, M. Ogiwara, and O. Watanabe,\n                      How hard are sparse sets?\n                      , in Proceedings of the Seventh Annual Structure in Complexity Theory Conference, IEEE Computer Society Press, Piscataway, NJ, 1992, pp. 222\u2013238."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00340-1"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.09.001"},{"key":"R13","first-page":"24","volume":"36","author":"Hitchcock J. M.","year":"2005","journal-title":"SIGACT News","ISSN":"https:\/\/id.crossref.org\/issn\/0163-5700","issn-type":"print"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90029-1"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910010"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116827"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90020-J"},{"key":"R18","unstructured":"J. H. Lutz,\n                      The quantitative structure of exponential time\n                      , in Complexity Theory Retrospective II, L. A. Hemaspaandra and A. L. Selman, eds., Springer, New York, 1997, pp. 225\u2013254."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701417723"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200310127"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792237498"},{"key":"R22","first-page":"64","volume":"68","author":"Lutz J. H.","year":"1999","journal-title":"Bull. Eur. Assoc. Theoret. Comput. Sci. EATCS","ISSN":"https:\/\/id.crossref.org\/issn\/0252-9742","issn-type":"print"},{"key":"R22","unstructured":"Also in\n                      Current Trends in Theoretical Computer Science: Entering the $21$st Century\n                      , World Scientific Publishing, River Edge, NJ, 2001, pp. 83\u2013101."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321547"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"R25","unstructured":"E. Mayordomo.\n                      Personal communication\n                      , 2002."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0220030"},{"key":"R27","unstructured":"O. Watanabe,\n                      Polynomial time reducibility to a set of small density\n                      , in Proceedings of the Second Structure in Complexity Theory Conference, IEEE Computer Society, Piscataway, NJ, 1987, pp. 138\u2013146."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90040-6"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/050647517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:25Z","timestamp":1787336785000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/050647517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/050647517"],"URL":"https:\/\/doi.org\/10.1137\/050647517","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}