Sabrina Schewtschenko, Undirected Graph Connectivity (USTCON) in Logspace

Sabrina Schewtschenko
Undirected Graph Connectivity (USTCON) in Logspace

In 2005 Omer Reingold proved that the USTCON (Undirected st-connectivity) is solvable in log-space and thus the classes SL and L are the same. Reingold introduced the new technique 'rotation map' to represent graphs in a handsome way and thus was able to state an algorithm which solves the USTCON problem in expander graphs in log-space. Now we are confronted to build up out of a given arbitrary graph an expander graph. To come up with this task we use the techniques 'powering' of a graph and the Reingold's 'zig-zag-product'. The required proves are given by linear algebra, due to the fact that we can represent graphs always by their associated matrix.