Following some recent applications by Mamoru Tanaka and Laurent Miclo, I was asked where there is a short, no-frills, self-contained, and (possibly) quantitatively non-optimal proof of the higher-order Cheeger inequalities from our paper with… 886 more words

## Tags » Spectral Partitioning

#### CS359G Lecture 4: Spectral Partitioning

*In which we prove the difficult direction of Cheeger’s inequality.*

As in the past lectures, consider an undirected -regular graph , call its adjacency matrix, and its scaled adjacency matrix. 905 more words

#### Lecture 4: Conformal mappings, circle packings, and spectral geometry

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

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

#### Max Cut-Gain and the Smallest Eigenvalue

In June, I wrote about my work on using spectral partitioning to approximate Max Cut.

I have now posted a revised paper with a couple new things. 466 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

#### Max Cut and the Smallest Eigenvalue

In the Max Cut problem, we are given an undirected graph and we want to find a partition of the set of vertices such that as many edges as possible have one endpoint in and one endpoint in , and are hence cut by the partition. 662 more words