USA - 2014
For contributions to the study of pseudorandomness, derandomization, and cryptography.
ACM Grace Murray Hopper Award
Israel - 2005
For his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs.
Dr. Omer Reingold's paper, Undirected ST-Connectivity in Log-Space, solved one of the most fundamental and central problems in computational complexity, efficiently finding whether there is a path from S to T in a graph. In this paper, Reingold proved a hard theorem that resolves a longstanding, natural problem: that of determining the space complexity of undirected ST-connectivity (thus proving L = SL). For more than 25 years, top theoretical computer science researchers and others have proven partial results aimed at showing that undirected ST-connectivity can be solved deterministically using logarithmic space (the minimal amount of memory one can hope for). Reingold ended this quest.