Abstract:

Suppose that every vertex of an n-vertex graph G = (V,E) of maximum degree Delta hosts a processor. These processors wake up simultaneously and communicate in discrete rounds. In each round each vertex is allowed to send an arbitrarily large message to all its neighbors. We are interested in coloring this graph with a relatively few colors within a small number of rounds. At the end of the algorithm each vertex needs to know its own color.

This problem is closely related to problems of computing a maximal independent set and a maximal matching in the distributed setting.

In this talk I plan to overview the rich history of the research on these problems, to mention the most important known results, and describe some of the basic techniques which are used to achieve them. Then I will turn to my own recent work on both deterministic (joint with Barenboim, JACM'11) and randomized (joint with Barenboim, Pettie and Schneider, FOCS'12) variants of these problems. Specifically, I will show an outline of the deterministic Delta^{1+eps}-coloring algorithm that requires polylogarithmic in n number of rounds . (Here eps > 0 is an arbitrarily small constant.) This result solves an open problem posed by Linial in 1987.

If time permits I will also show an outline of a randomized (Delta+1)-coloring algorithm that requires O(log Delta) + exp{O(sqrt{loglog n})} number of rounds.

There is a huge number of open problems in this area. During the talk I will present and discuss some of them.

Host: Seth Pettie