Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders
Xue Chen · 2015
We study the problem of approximating the quality of a disperser. A bipartite graph G on ([N], [M]) is a (ρN, (1 – δ)M)-disperser if for any subset S ⊆ [N] of size ρN, the neighbor set Γ(S) contains at least (1 – δ)M distinct vertices. Our main results are strong integrality gaps in the Lasserre hierarchy and an approximation algorithm for dispersers.