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)

at A-201 (STCS Seminar Room)

Description |
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). |