Abstract
We study the robust  à la Chakrabarti, Cormode, and McGregor [STOC'08]  communication complexity of the maximum bipartite matching problem. The edges of an adversarially chosen nvertex bipartite graph G are partitioned randomly between Alice and Bob. Alice has to send a single message to Bob, using which Bob has to output an approximate maximum matching of G. We are particularly interested in understanding the best approximation ratio possible by protocols that use a nearoptimal message size of n ⋅ polylog(n).
The communication complexity of bipartite matching in this setting under an adversarial partitioning is wellunderstood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA'12] gave a rac{2} {3}approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a nearlinear communication. The complexity of the robust version, i.e., with a random partitioning of the edges, however remains wide open. The best known protocol, implied by a very recent randomorder streaming algorithm of the authors [ICALP'21], uses O(n log n) communication to obtain a (rac{2} {3} + ε₀)approximation for a constant ε₀ ∼ 10^{14}. The best known lower bound, on the other hand, leaves open the possibility of all the way up to even a (1ε)approximation using nearlinear communication for constant ε > 0.
In this work, we give a new protocol with a significantly better approximation. Particularly, our protocol achieves a 0.716 expected approximation using O(n) communication. This protocol is based on a new notion of distributiondependent sparsifiers which give a natural way of sparsifying graphs sampled from a known distribution. We then show how to lift the assumption on knowing the graph’s distribution via minimax theorems. We believe this is a particularly powerful method of designing communication protocols and might find further applications.
BibTeX  Entry
@InProceedings{assadi_et_al:LIPIcs.APPROX/RANDOM.2021.48,
author = {Assadi, Sepehr and Behnezhad, Soheil},
title = {{On the Robust Communication Complexity of Bipartite Matching}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {48:148:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14741},
URN = {urn:nbn:de:0030drops147411},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.48},
annote = {Keywords: Maximum Matching, Communication Complexity, RandomOrder Streaming}
}
Keywords: 

Maximum Matching, Communication Complexity, RandomOrder Streaming 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) 
Issue Date: 

2021 
Date of publication: 

15.09.2021 