Institute of Information Science, Academia Sinica

The (Delta+1)-coloring problem and the MIS (maximal independent set) problem are fundamental symmetry-breaking problems in distributed computing. 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([@BackSlash]sqrt{log Delta} ) + 2^{O([@BackSlash]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, [@BackSlash]sqrt{log n}) lower bound by Kuhn, Moscibroda, and Wattenhofer. Finally, I will address some open problems.