Abstract:
This talk will be a presentation of a paper by Omer Reingold that won the Best Paper Award at STOC 2005.
The author of the paper presents a deterministic log-space algorithm that solves st-connectivity in undirected graphs. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations).