The winners of the 2020 Principles of Distributed Computing Doctoral Dissertation Award are
- Dr. Yi-Jun Chang for his dissertation Locality of Distributed Graph Problems written under the supervision of Prof. Seth Pettie at the University of Michigan.
- Dr. Yannic Maus for his dissertation The Power of Locality: Exploring the Limits of Randomness in Distributed Computing written under the supervision of Prof. Fabian Kuhn at the University of Freiburg.
The theses of Dr. Chang and Dr. Maus have played a key role in the recent, rapid development of the theory of distributed graph algorithms and network computing. Both of the theses have significantly advanced our understanding of the distributed computational complexity of many key problems (e.g. graph coloring and splitting). In addition, they have made groundbreaking contributions to the development of distributed computational complexity theory in general.
These theses have introduced highly insightful concepts (e.g. the SLOCAL model) and new intriguing graph problems (e.g. hierarchical coloring), they have developed novel proof techniques (e.g. pumping arguments), and they have proved surprising results (e.g. gap theorems and completeness). Put together, they have dramatically changed the way in which researchers working in this field reason about distributed computational complexity. The theses have been a driving force in this research area, and the concepts and ideas introduced in these theses have already led to major breakthroughs.
The work presented in both dissertations has been published in a remarkably large number of papers, has been presented at top conferences, and has received wide recognition, including multiple best paper awards.
Due to the highly significant role these two theses have played in the development of the field of distributed computing, the award committee unanimously selected them as the winners of the 2020 Principles of Distributed Computing Doctoral Dissertation Award, presented at DISC 2020.
The award is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). It is presented annually, with the presentation taking place alternately at PODC and DISC.
2020 Award Committee:
- Faith Ellen, University of Toronto
- Pierre Fraigniaud, CNRS and University Paris Diderot
- David Peleg (chair), The Weizmann Institute
- Jukka Suomela, Aalto University
