New Hardness Results for the LOCAL Model via a Simple Self-Reduction

Very recently, Khoury and Schild [FOCS 2025] showed that any randomized LOCAL algorithm that solves maximal matching requires Ω(min{log Δ, logΔ n}) rounds, where n is the number of nodes in the graph and Δ is the maximum degree. This result is shown through a new technique, called round elimination via self-reduction. The lower bound proof is beautiful and presents very nice ideas. However, it spans more than 25 pages of technical details, and hence it is hard to digest and generalize to other problems.