Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders

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$, the neighbor set $\mathrm{\Gamma }(S)$ contains at least $(1-\delta )M$ distinct vertices. Our main results are strong integrality gaps in the Lasserre hierarchy and an approximation algorithm for dispersers. \begin{enumerate} \item For any $\alpha >0$, $\delta >0$, and a random bipartite graph $G$ with left degree $D=O(\log N)$, we prove that the Lasserre hierarchy cannot distinguish whether $G$ is an $(N^{\alpha },(1-\delta )M)$-disperser or not an $(N^{1-\alpha },\delta M)$-disperser. \item For any $\rho >0$, we prove that there exist infinitely many constants $d$ such that the Lasserre hierarchy cannot distinguish whether a random bipartite graph $G$ with right degree $d$ is a $(\rho N, (1-(1-\rho)^d)M)$-disperserornota$(\rho N, (1-\Omega(\frac{1-\rho}{\rho d + 1-\rho}))M)$-disperser. We also provide an efficient algorithm to find a subset of size exact $\rho N$ that has an approximation ratio matching the integrality gap within an extra loss of $\frac{\min \{\frac{\rho }{1-\rho },\frac{1-\rho }{\rho }\}}{\log d}$. \end{enumerate} Our method gives an integrality gap in the Lasserre hierarchy for bipartite expanders with left degree~$D$. $G$ on $([N],[M])$ is a $(\rho N,a)$-expander if for any subset $S\subseteq [N]$ of size $\rho N$, the neighbor set $\mathrm{\Gamma }(S)$ contains at least $a\cdot \rho N$ distinct vertices. We prove that for any constant $ϵ>0$, there exist constants ${ϵ}^{\mathrm{\prime }}<ϵ,\rho ,$ and $D$ such that the Lasserre hierarchy cannot distinguish whether a bipartite graph on $([N],[M])$ with left degree $D$ is a $(\rho N, (1-\epsilon’)D)$-expanderornota$(\rho N, (1-\epsilon)D)$-expander.