|
2005 – Omer Reingold
Weizmann Institute, Israel (2005)
Citation
For his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs. Press Release
Full Citation
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.
|
