Omer Reingold

Author of Reingold's Algorithm, which resolved the memory-complexity of finding paths in undirected graphs, Reingold is cited for finding a solution to a more than 25-year quest by expert theoretical computer science researchers and others. He addressed the problem of finding paths to connect vertices in undirected graphs (i.e. finding paths in a three-dimensional maze). The time complexity of this key graph problem had been well understood for decades. Reingold's theorem resolved the memory-complexity of the problem by showing that connectivity in undirected graphs admits an extremely memory-efficient algorithm. The memory used by Reingold's algorithm was comparable to the memory needed to store simply the name of a single vertex of the graph.

One of the most important consequences of this theorem was demonstrating the equivalence of two complexity classes (i.e. sets of computational problems with the same bounds on time and space) known as SL and L (Symmetric Logspace and Deterministic Logspace). This fundamental result greatly advanced the understanding of the power of nondeterminism and randomization over deterministic memory-bounded computation.