# Lecture Notes on the ARV Algorithm for Sparsest Cut

arXiv: https://arxiv.org/abs/1607.00854 · HTML: https://mlsanity.com/paper/1607.00854/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2016.

## Built on by (most cited first, 1 of 1)

- [Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues](https://mlsanity.com/paper/2306.09128/) (2023)

## Abstract (arXiv)

One of the landmarks in approximation algorithms is the O(√log n)-approximation algorithm for the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The algorithm is based on a semidefinite program that finds an embedding of the nodes respecting the triangle inequality. Their core argument shows that a random hyperplane approach will find two large sets of Theta(n) many nodes each that have a distance of Theta(1/√log n) to each other if measured in terms of |· |22. Here we give a detailed set of lecture notes describing the algorithm. For the proof of the Structure Theorem we use a cleaner argument based on expected maxima over k-neighborhoods that significantly simplifies the analysis.