Prof. Omer Reingold

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.