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

26/05/2016 - 12:00

Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the distributed 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.  In this talk we show that these exponential gaps are necessary and establish connections between the deterministic and randomized complexities in the LOCAL model.  Each of our results has a very compelling take-away message:

1. Fast Delta-coloring of trees requires random bits.

2. Randomized lower bounds imply higher deterministic lower bounds.

3. Deterministic lower bounds imply randomized lower bounds.

Joint work with Yi-Jun Chang and Seth Pettie