All reports by Author Satyen Kale:

__
TR07-131
| 16th November 2007
__

Satyen Kale#### Boosting and hard-core set constructions: a simplified approach

__
TR07-076
| 25th July 2007
__

Satyen Kale, C. Seshadhri#### Testing Expansion in Bounded Degree Graphs

Revisions: 1

Satyen Kale

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

Satyen Kale, C. Seshadhri

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