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

Abstract: 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 / log log \Delta, \sqrt{log n/ \log log n})\) lower bound by Kuhn, Moscibroda, and Wattenhofer. Finally, I will address some open problems.

 

Bio: Hsin-Hao Su is a postdoctoral associate in Nancy Lynch's Group at MIT. He graduated from University of Michigan in 2015 (advisor: Seth Pettie). His thesis received the 2016 Principle of Distributed Computing Doctoral Dissertation Award. His research interests include graph algorithms in both sequential and distributed models and bio-inspired algorithms.