Hsin-Hao Su: Distributed (Delta+1)-Coloring in Sublogarithmic Rounds

Friday, November 6, 2015 - 1:00pm to 2:30pm
Hsin-Hao Su

The (Delta+1)-coloring problem and the MIS (maximal independent set) problem are fundamental distributed symmetry-breaking problems. Although many faster algorithms are known when the maximum degree, Delta, is small, the best running time for both problems remain O(log n) rounds since Luby. In this talk, I will review some randomized approaches for distributed coloring. Then I will talk about a recent joint work with David Harris and Johannes Schneider, which shows that a (Delta+1)-coloring can be computed with high probability in O(\sqrt{log Delta} ) + 2^{O(\sqrt{log log n})} rounds. It also implies the (Delta+1)-coloring problem is easier than the MIS problem, due to its min( log Delta, \sqrt{log n}) lower bound by Kuhn, Moscibroda, and Wattenhofer. Finally, I will address some open problems.