School of Technology and Computer Science Seminars

On the Communication and Streaming Complexity of Maximum Bipartite Matching

by Sumedh Vinod Tirodkar (School of Technology and Computer Science, TIFR)

Friday, April 21, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
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).