Theory Seminar

New Approximation Bounds for Small-Set Vertex Expansion

Suprovat GhoshalNorthwestern / TTIC

WHERE:

3725 Beyster Building

WHEN:

Friday, January 12, 2024 @ 2:00 pm - 3:00 pm
This event is free and open to the publicAdd to Google Calendar

(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.

Organizer

Greg Bodwin

Organizer

Euiwoong Lee

Events

Theory Seminar

New Approximation Bounds for Small-Set Vertex Expansion

Organizer

Organizer