GT AlgoDist, «Universal Exploration Sequences and Undirected s-t Connectivity», Sébastien Bouchard
Sébastien Bouchard
Title: Universal Exploration Sequences and Undirected s-t Connectivity
Abstract:
Undirected s-t connectivity (USTCON) is a SL-complete problem (SL stands for Symmetric Log-space). During decades, researchers tried to propose a log-space algorithm for this problem. It would prove that SL=L. This was achieved in 2005 by Omer Reingold. His USTCON algorithm can also be used to construct sequences of integers called universal exploration sequences (UXS) which, given the number of vertices of a graph, can guide a deterministic walk, of polynomial length, allowing to visit all its nodes.
The talk will present USTCON, UXS, and provide a high-level view of Reingold's algorithm and its use to construct UXS.