An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
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. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. We prove that these exponential …