Yi-Jun Chang, a graduate student in the Computer Science and Engineering program, has received a Chia-Lun Lo Fellowship for 2016-17. Chang is currently a second year PhD student working with Prof. Seth Pettie.
Chang’s research interest is in complexity theory of distributed computing. One of the central problems of complexity theory is to determine the value of random bits. In the centralized computation model, it is widely believed that P=BPP, i.e., randomness doesn’t help at all, up to polynomial differences. He investigated the same problem in the distributed world, and demonstrated the first instance of exponential separation between the randomized and deterministic complexities in the distributed LOCAL model. The Time Hierarchy Theorem informally says that a Turing machine can solve more problems given more time. He showed that, surprisingly, this is not true in the distributed world by demonstrating a “gap” in the possible deterministic LOCAL complexities.
The Chia-Lun Lo Fellowship assists outstanding students in Rackham programs who have earned a previous degree from a university in Taiwan and who may be ineligible for other kinds of support because of citizenship. To be eligible, international graduate students must have successfully completed one year of graduate study as a master’s or precandidate student. Nominees must have a strong academic record, be making good progress toward the degree, and demonstrate outstanding academic and professional promise.