An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring.…