On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths

Yu Cheng, Tianle Jiang, Pachara Sawettamalya +1

We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new $\tilde{O}(n^{3/2})$-bit protocol fo…