The Edsger W. Dijkstra Prize in Distributed Computing is awarded for outstanding papers on the principles of distributed computing, whose significance and impact on the theory or practice of distributed computing have been evident for at least a decade. It is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The prize is presented annually, with the presentation taking place alternately at PODC and DISC. The committee decided to award the 2025 Edsger W. Dijkstra Prize in Distributed Computing to
Moni Naor and Larry Stockmeyer (1948 – 2004)
for their paper
“What Can Be Computed Locally?“
which originally appeared in the Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC) 1993 and then later in the SIAM Journal on Computing, volume 24, issue 6, 1995.
This paper forms the foundation of our modern understanding of
distributed computational complexity, particularly the locality of graph
problems. While much of the early work on distributed graph algorithms
and locality focused on specific individual problems, Naor and
Stockmeyer took the first step toward systematically studying the
distributed computational complexity of entire families of problems. Their work initiated a research program that remains highly active even
30 years later. This is a paper that continues to profoundly influence
our research community, and its impact is increasingly reaching other
areas as well, including quantum information theory, measurable
combinatorics, stochastic processes, neural networks, and game theory.
2025 Award Committee:
Hagit Attiya, Technion, Israel
Christian Cachin, University of Bern, Switzerland
Dariusz R. Kowalski, Augusta University, USA
Fabian Kuhn (chair), University of Freiburg, Germany
Yoram Moses, Technion, Israel
Paul Spirakis, University of Liverpool, UK