Tags » Spectral Partitioning

No frills proof of higher-order Cheeger inequality

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


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


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