Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SATYEN KALE:
All reports by Author Satyen Kale:

TR07-131 | 16th November 2007
Satyen Kale

Boosting and hard-core set constructions: a simplified approach

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


TR07-076 | 25th July 2007
Satyen Kale, C. Seshadhri

Testing Expansion in Bounded Degree Graphs

Revisions: 1

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>




ISSN 1433-8092 | Imprint