Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching

We show that there is no randomized LOCAL algorithm for maximal matching (MM) that takes o(min(log D, sqrt(log n))) rounds, even on regular graphs and trees. This improves upon the KMW bound from 21 years ago and shows a surprising separation between MM and MIS on trees, among other implications.