# New Approximation Bounds for Small-Set Vertex Expansion

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Nov 2023.

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

- [Active Learning on Adversarially Corrupted Graphs](https://mlsanity.com/paper/2607.04869/) (2026)

## Abstract (arXiv)

The vertex expansion of the graph is a fundamental graph parameter. Given a graph G=(V,E) and a parameter δ ∈ (0,1/2], its δ-Small-Set Vertex Expansion (SSVE) is defined as [ minS : |S| = δ |V| frac|partialV(S)| min  |S|, |Sc|   ] where partialV(S) is the vertex boundary of a set S. The SSVE~problem, in addition to being of independent interest as a natural graph partitioning problem, is also of interest due to its connections to the Strong Unique Games problem. We give a randomized algorithm running in time n^sf poly(1/δ), which outputs a set S of size Theta(δ n), having vertex expansion at most [ maxleft(O(√φ^* log d log (1/δ)) , tildeO(dlog2(1/δ)) · φ^* right), ] where d is the largest vertex degree of the graph, and φ^* is the optimal δ-SSVE. The previous best-known guarantees for this were the bi-criteria bounds of tildeO(1/δ)√φ^* log d and tildeO(1/δ)φ^* √log n due to Louis-Makarychev [TOC'16]. Our algorithm uses the basic SDP relaxation of the problem augmented with rm poly(1/δ) rounds of the Lasserre/SoS hierarchy. Our rounding algorithm is a combination of the rounding algorithms of Raghavendra-Tan [SODA'12] and Austrin-Benabbas-Georgiou [SODA'13]. A key component of our analysis is novel Gaussian rounding lemma for hyperedges which might be of independent interest.