Linial's Lower Bound Made Easy

Abstract

Linial's seminal result shows that any deterministic distributed algorithm that finds a $3$-colouring of an $n$-cycle requires at least ${\log }^{\ast }(n)/2-1$ communication rounds. We give a new simpler proof of this theorem.

3 pages, 1 figure