The Taub Faculty of Computer Science Events and Talks

It is widely known that in the well-studied \LOCAL model of distributed computing, introduced by Linial [FOCS '87], many of the classic distributed graph problems (including maximal independent set (MIS) and MaxDegree+1-vertex coloring), have very efficient (and simple) randomized but exponentially slower deterministic algorithms. Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms.

We present the recent advances in understanding this gap and show how randomization is used in solving these problems. Perhaps most surprisingly, we show that the existence of efficient deterministic algorithms for these classic problems reduces to finding an efficient deterministic algorithm for the following rather rudimentary looking graph coloring problem: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution, deterministically we do not know how to solve it efficiently and doing so would be a major breakthrough in the area.