## 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 n-vertex 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 near-optimal message size of n · polylog (n). The communication complexity of bipartite matching in this setting under an adversarial partitioning is well-understood. In their beautiful paper, Goel, Kapralov, and Khanna [SODA'12] gave a ^{2}/3-approximate protocol with O(n) communication and showed that this approximation is tight unless we allow more than a near-linear 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 random-order streaming algorithm of the authors [ICALP'21], uses O(n log n) communication to obtain a (^{2}/3 + ε0)-approximation for a constant ε0 ∼ 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 near-linear 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 distribution-dependent 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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2021 |

Editors | Mary Wootters, Laura Sanita |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772075 |

DOIs | |

State | Published - Sep 1 2021 |

Event | 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 - Virtual, Seattle, United States Duration: Aug 16 2021 → Aug 18 2021 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 207 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2021 and 25th International Conference on Randomization and Computation, RANDOM 2021 |
---|---|

Country/Territory | United States |

City | Virtual, Seattle |

Period | 8/16/21 → 8/18/21 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Communication complexity
- Maximum matching
- Random-order streaming