Theory Seminar

New Approximation Bounds for Small-Set Vertex Expansion

Suprovat GhoshalNorthwestern / TTIC
3725 Beyster BuildingMap
(Passcode: 430018)
The vertex expansion of the graph is a fundamental graph parameter. Given a graph G=(V,E) and a parameter \delta \in (0,1/2], its \delta-Small-Set Vertex Expansion (SSVE) is defined as
 \min_{S : |S| = \delta |V|}  \frac{|\partial^V(S)|}{|S|}

where \partial^V(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 StrongUniqueGames Problem (Ghoshal-Louis’21). We give a randomized algorithm running in time n^{{\sf poly}(1/\delta)}, which outputs a set S of size \Theta(\delta n), having vertex expansion at most

 \max\left(O(\sqrt{\phi^* \log d \log (1/\delta)}) , \tilde{O}(d\log^2(1/\delta)) \cdot \phi^* \right)

where d is the largest vertex degree of the graph, and \phi^* is the optimal \delta-SSVE. The previous best-known guarantees for this were the bi-criteria bounds of \tilde{O}(1/\delta)\sqrt{\phi^* \log d}  and \tilde{O}(1/\delta)\phi^* \sqrt{\log n} due to Louis-Makarychev [TOC’16].

Our algorithm uses the basic SDP relaxation of the problem augmented with {\rm poly}(1/\delta) rounds of the Lasserre/SoS hierarchy. Our rounding algorithm is a combination of the rounding algorithms of Raghavendra-Tan’12 and Austrin-Benabbas-Georgiou’13. A key component of our analysis is novel Gaussian rounding lemma for hyperedges, which might be of independent interest.

This is joint work with Anand Louis.


Greg Bodwin


Euiwoong Lee