ICS Theory Group

ICS 269, Fall 2005: Theory Seminar

Undirected ST-Connectivity in Log-Space

Nodari Sitchinava

October 28, 2005, in CS 259


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).