Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders

Xue Chen

We study the problem of approximating the quality of a disperser. A bipartite graph $G$ on $([N],[M])$ is a $(\rho N,(1-\delta )M)$-disperser if for any subset $S\subseteq [N]$ of size $\rho N$,…