Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-131 | 16th November 2007 00:00

Boosting and hard-core set constructions: a simplified approach

RSS-Feed




TR07-131
Authors: Satyen Kale
Publication: 16th December 2007 05:00
Downloads: 5401
Keywords: 


Abstract:

We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use this boosting algorithm to show the existence of hard-core sets matching the best parameters of Klivans and Servedio's construction.



ISSN 1433-8092 | Imprint