CSE alumnus Hsin-Hao Su selected for Principles of Distributed Computing Dissertation Award

CSE PhD alumnus Hsin-Hao Su has been selected as the recipient of a 2016 Principles of Distributed Computing Doctoral Dissertation Award for his dissertation, “Algorithms for Fundamental Problems in Computer Networks.”

The Principles of Distributed Computing Doctoral Dissertation Award was created in 2012 to acknowledge and promote outstanding research by doctoral students on the principles of Distributed Computing. The award is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC).

Hsin-Hao’s thesis provides efficient algorithms for fundamental graph problems that arise in networks, in both sequential and distributed settings. Among the latter, the most prominent are his results concerning graph coloring. He showed that numerous existential results in graph theory can be viewed as distributed algorithms with a tiny probability of success (guaranteed by the Lovasz Local Lemma) and that a fast distributed algorithm for the constructive LLL could be used to amplify the success probability to nearly 1. Hsin-Hao presented a O(log n)- time randomized algorithm for the LLL, and illustrated how it could be applied to graph coloring problems where the existence of the coloring is not obvious. Moser and Tardos observed that any LLL algorithm in their “resampling” framework requires Ω(log n) time, so this result is optimal within a natural design space. Hsin-Hao used his LLL algorithm to establish an O(log n)-time algorithm for (4+o(1))Δ/ln Δ−coloring triangle-free graphs. This result more than any other exhibits the technical virtuosity of Hsin-Hao: he discovered not only a great algorithm, but a new bound on the chromatic number of triangle-free graphs.

Before Hsin-Hao’s work many symmetry-breaking problems appeared to have similar complexity: (Δ+1)−coloring seemed similar to the Maximal Independent Set (MIS) problem and (2Δ−1)−edge coloring seemed similar to Maximal Matching. Hsin-Hao developed new tools for analyzing randomized coloring algorithms in locally sparse graphs, one consequence of which is that (2Δ−1)−edge coloring is provably easier than maximal matching.

Dr. Su is now a postdoctoral associate in Nancy Lynch’s Theory of Distributed Systems Group in the EECS department at Massachusetts Institute of Technology. He received the Ph.D. degree in Computer Science and Engineering in 2015 at the University of Michigan, Ann Arbor under the guidance of Prof. Seth Pettie.