Distributed (Delta+1)-Coloring in Sublogarithmic Rounds
- 講者Hsin-Hao Su 博士 (Computer Science and Artificial Intelligence Laboratory, MIT)
邀請人:鐘楷閔 - 時間2015-12-24 (Thu.) 10:00 ~ 12:00
- 地點資訊所新館106演講廳
摘要
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.