@online{Coupette_arXiv2002.06005,
TITLE = {A Breezing Proof of the {KMW} Bound},
AUTHOR = {Coupette, Corinna and Lenzen, Christoph},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2002.06005},
EPRINT = {2002.06005},
EPRINTTYPE = {arXiv},
YEAR = {2020},
ABSTRACT = {In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW)<br>proved a hardness result for several fundamental graph problems in the LOCAL<br>model: For any (randomized) algorithm, there are input graphs with $n$ nodes<br>and maximum degree $\Delta$ on which $\Omega(\min\{\sqrt{\log n/\log \log<br>n},\log \Delta/\log \log \Delta\})$ (expected) communication rounds are<br>required to obtain polylogarithmic approximations to a minimum vertex cover,<br>minimum dominating set, or maximum matching. Via reduction, this hardness<br>extends to symmetry breaking tasks like finding maximal independent sets or<br>maximal matchings. Today, more than $15$ years later, there is still no proof<br>of this result that is easy on the reader. Setting out to change this, in this<br>work, we provide a fully self-contained and $\mathit{simple}$ proof of the KMW<br>lower bound. The key argument is algorithmic, and it relies on an invariant<br>that can be readily verified from the generation rules of the lower bound<br>graphs.<br>},
}