ARV on Abelian Cayley Graphs

Continuing from the previous post, we are going to prove the following result: let ${G}$ be a ${d}$-regular Cayley graph of an Abelian group, ${\phi(G)}$ be the normalized edge expansion of ${G}$, ${ARV(G)}$ be the value of the ARV semidefinite programming relaxation of sparsest cut on ${G}$ (we will define it below), and ${\lambda_2(G)}$ be the second smallest normalized Laplacian eigenvalue of ${G}$. Then we have

$\displaystyle \lambda_2 (G) \leq O(d) \cdot (ARV (G))^2 \ \ \ \ \ (1)$

which, together with the fact that ${ARV(G) \leq 2 \phi(G)}$ and ${\phi(G) \leq \sqrt{2 \lambda_2}}$, implies the Buser inequality

$\displaystyle \lambda_2 (G) \leq O(d) \cdot \phi^2 (G) \ \ \ \ \ (2)$

and the approximation bound

$\displaystyle \phi(G) \leq O(\sqrt d) \cdot ARV(G) \ \ \ \ \ (3)$

The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).

CS 294 Lecture 14: ARV Analysis, Part 3

In which we complete the analysis of the ARV rounding algorithm

We are finally going to complete the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio ${O(\sqrt {\log |V|})}$.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

CS294 Lecture 13: ARV Analysis, cont’d

In which we continue the analysis of the ARV rounding algorithm

We are continuing the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio ${O(\sqrt {\log |V|})}$.

In previous lectures, we reduced the analysis of the algorithm to the following claim.

CS359G Lecture 14: ARV Rounding

In which we begin to discuss the Arora-Rao-Vazirani rounding procedure.

Recall that, in a graph ${G=(V,E)}$ with adjacency matrix ${A}$, then ARV relaxation of the sparsest cut problem is the following semidefinite program.

$\displaystyle \begin{array}{lll} {\rm minimize} & \frac 1 {2|E|} \sum_{u,v} A_{u,v} || {\bf x}_u - {\bf x}_v ||^2\\ {\rm subject\ to}\\ & \sum_{u,v} || {\bf x}_u - {\bf x}_v ||^2 = {|V|^2}\\ & || {\bf x}_u - {\bf x}_v||^2 \leq || {\bf x}_u - {\bf x}_w||^2 + || {\bf x}_w - {\bf x}_v||^2 & \forall u,v,w \in V\\ & \mbox{} {\bf x}_u \in {\mathbb R}^d & \forall u\in V \end{array}$

If we denote by ${ARV(G)}$ the optimum of the relaxation, then we claimed that

$\displaystyle ARV(G) \leq \phi(G) \leq O(\sqrt{\log |V|}) \cdot ARV(G)$

where the first inequality follows from the fact that ${ARV(G)}$ is a relaxation of ${\phi(G)}$, and the second inequality is the result whose proof we begin to discuss today.