The committee for the 2025 Principles of Distributed Computing Doctoral Dissertation Award has decided to share the award between two recipients:
- Dr. Christoph Grunau, for his dissertation Sampling with Certainty in Distributed and Parallel Computations.
- Dr. Vaclav Rozhon, for his dissertation Local Complexity: New Results and Bridges to Other Fields.
Dr. Grunau and Dr. Rozhon both completed their Doctor of Sciences degrees at ETH Zürich under the supervision of Mohsen Ghaffari and Angelika Steger.
Dr. Grunau’s dissertation describes a local rounding mechanism for transforming many randomized distributed graph algorithms into deterministic algorithms with very little loss in efficiency, using only local information. This gives very efficient deterministic algorithms in the LOCAL model for such fundamental problems as maximal independent set, maximal matching, and graph coloring, resolving numerous long-standing open problems. In the context of parallel algorithms, the dissertation provides a parallel mechanism for derandomizing parallel algorithms that rely on Chernoff-like bounds, giving a deterministic parallel algorithm for set balancing that for the first time achieves work bounds close to those long known for sequential algorithms.
Dr. Rozhon’s dissertation describes numerous deep results for the LOCAL model. These include an improved version of the author’s breakthrough polylogarithmic-time deterministic algorithm for network decomposition; speedup theorems that provide the final step in completely classifying locally-checkable labeling problems on trees and grids; and a surprising connection between local problems on regular trees and the field of descriptive combinatorics. The dissertation is also noteworthy for its detailed and comprehensive survey of recent progress in the LOCAL model both the author and others.
The committee has also chosen to give an Honorable Mention to
- Dr. Sean Garnet Ovens, for his dissertation The Space Complexity of Asynchronous Algorithms from Bounded Size Base.
Dr. Ovens completed his Doctor of Philosophy degree at the University of Toronto under the supervision of Faith Ellen.
In his dissertation, he describes a new combinatorial technique for proving lower bounds on the space complexity of shared-memory objects implemented from base objects of bounded size. This gives nearly-tight lower bounds on the space complexity of a large class of snapshot-like objects and, in conjunction with a novel valency argument, provides strong lower bounds on the space complexity of obstruction-free consensus implemented from bounded-size swap objects. The final chapter of the dissertation contains a detailed analysis of the space complexity of k-set agreement using unbounded-size swap objects, proving new upper and lower bounds for this problem.
The 2025 Principles of Distributed Computing Doctoral Dissertation Award Committee:
- Dan Alistarh, IST Austria
- James Aspnes (chair), Yale University
- Pierre Fraigniaud, IRIF, Université Paris Cité, CNRS
- Cyril Gavoille, Université de Bordeaux
- Danny Hendler, Ben-Gurion University
- Petr Kuznetsov, INFRES, Telecom Paris, Institut Polytechnique de Paris