In Lecture 2, we used spectral partitioning to rule out the existence of a strong parallel repetition theorem for unique games. In practice, spectral methods are a very successful heuristic for graph partitioning, and in the present lecture we’ll see how to analyze these partitioning algorithms for some common families of graphs. 1,349 more words

## Tags » Cheeger's Inequality

#### Lecture 2: Spectral partitioning and near-optimal foams

In the last lecture, we reduced the problem of cheating in (the k-times repeated m-cycle game) to finding a small set of edges in whose removal eliminates all topologically non-trivial cycles. 1,228 more words

#### Parallel repetition, unique games, and spectral partitioning

Yesterday, Anup Rao pointed me to these two remarkably beautiful papers, which made my morning coffee taste a little better, and the Boston sun feel a bit warmer. 123 more words