Semi-Robust Communication Complexity of Maximum Matching
Abstract
We study the one-way two-party communication complexity of \(\mathsf{Maximum\ Matching}\) in the semi-robust setting where the edges of a maximum matching are randomly partitioned between Alice and Bob, but all remaining edges of the input graph are adversarially partitioned between the two parties.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Distributed systems and fault tolerance
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 216–228
- Publication date
- 1 January 2026
- Language
- EN