Faculty Recruiting Support CICS

Towards the Locality of Vizing's Theorem

19 Apr
Friday, 04/19/2019 11:00am to 12:00pm
Computer Science Building Room 140
Theory Seminar

Vizing showed that it suffices to color the edges of a simple graph using Delta + 1 colors, where Delta is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Delta + \tilde{\sqrt{Delta}})-edge-coloring algorithm that runs in polylog(n) rounds by Chang et al. and the deterministic (Delta + polylog(n))-edge-coloring algorithm that runs in poly(Delta, log n) rounds by Ghaffari et al.

In this talk, I will present a randomized distributed edge-coloring algorithms that run in poly(log n, Delta) rounds that uses Delta + 2 colors, which is merely one more color than that of Vizing's Theorem. I will show the connection between the problem and an online, restricted version of balls-into-bins problem. If L is the maximum load of the bins, then it corresponds to using Delta + 2L - 1 colors to color the edges. We show how to achieve L=1 with randomization and L = O(log n / log log n) without randomization. Finally, I will conclude the talk with a few related open problems.

This is a joint work with Hoa Vu.

Faculty Host