“We study the robust communication complexity of maximum matching. Edges of an arbitrary n-vertex graph G are randomly partitioned between Alice and Bob independently and uniformly. Alice has to send a single message to Bob such that Bob can find an (approximate) maximum matching of the whole graph G. We specifically study the best approximation ratio achievable via protocols where Alice communicates only O˜(n) bits to Bob.”

Find the paper and full list of authors at ArXiv.