Seri Khoury

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

2025 · arXiv (Cornell University)

In this work, we present an $Ω\left(\min\{\log Δ, \sqrt{\log n}\}\right)$ lower bound for Maximal Matching (MM) in $Δ$-ary trees against randomized algorithms. By a folklore reduction, the same lower bound applies to Maximal Independent Set …