Aviad Rubinstein is the recipient of the Association for Computing Machinery (ACM) 2017 Doctoral Dissertation Award for his dissertation “Hardness of Approximation Between P and NP.” Honorable Mentions for the award went to Mohsen Ghaffari, who received his PhD from the Massachusetts Institute of Technology’s Department of Electrical Engineering and Computer Science (MIT EECS) and Stefanie Mueller, who received her PhD from the Hasso Plattner Institute (Germany).
In Ghaffari’s dissertation, “Improved Distributed Algorithms for Fundamental Graph Problems,” he presents novel distributed algorithms that significantly lower the costs of solving fundamental graph problems in networks, including structuring problems, connectivity problems, and scheduling problems. Ghaffari’s dissertation includes both breakthrough algorithmic contributions and interesting methodology. The first part of the dissertation presents a new maximal independent set (MIS) algorithm, which is a breakthrough because it achieves a better time bound than previous algorithms for this three-decades-old problem. The second part of the dissertation contains a collection of related results about vertex connectivity decompositions. Finally, in the third part of his dissertation, Ghaffari introduces a time-efficient algorithm for concurrent scheduling of multiple distributed algorithms. Ghaffari is an Assistant Professor of Computer Science at ETH Zurich. He received a PhD and SM in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology and received a double major in Computer Science and Electrical Engineering from Sharif University (Iran).
