Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
John M. Hitchcock · Lecture notes in computer science · 2006
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). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.