On the Communication and Streaming Complexity of Maximum Bipartite Matching

Consider the following communication problem. Alice holds a graph $G_A = (P, Q, E_A)$ and Bob holds a graph $G_B = (P, Q, E_B)$, where $|P| = |Q| = n$. Alice is allowed to send Bob a message $m$ that depends only on the graph $G_A$. Bob must then output a matching $M\subseteq E_A \cup E_B$. What is the minimum message size of the message $m$ that Alice sends to Bob that allows Bob to recover a matching of size at least $(1 - \epsilon)$ times the maximum matching in $G_A \cup G_B$? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a $(1 - \epsilon)$-approximate bipartite matching. Using connection to $\epsilon$-RS graphs, the authors show that for any $\delta>0$, a $(2/3+\delta)$-approximation requires a communication complexity of $n^{1+\Omega(1/\log\log n)}$. And thus, no one-pass semi-streaming algorithm can have a $(2/3+\delta)$-approximation ratio (authors: Ashish Goel, Michael Kapralov, Sanjeev Khanna).