Abstract:
We establish a relationship between the online mistake-bound model of learning and resource-bounded 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 (1995) and Lutz and Zhao (2000), and solves one of Lutz and Mayordomo's "Twelve Problems in Resource-Bounded Measure" (1999).

• SIAM Journal on Computing, 36(6):1696-1708, 2007.
  [DOI link | PostScript | PDF]

• Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science (Marseille, France, February 23-25, 2006), Lecture Notes in Computer Science 3884, pages 408-419. Springer-Verlag, 2006.
  [DOI link]

• Technical Report cs.CC/0512053, Computing Research Repository, 2005.
  Technical Report TR05-161, Electronic Colloquium on Computational Complexity, 2005.