Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-161 | 13th December 2005 00:00

Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

RSS-Feed




TR05-161
Authors: John Hitchcock
Publication: 23rd December 2005 17:54
Downloads: 2881
Keywords: 


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).



ISSN 1433-8092 | Imprint