Undirected Graph Connectivity in Log-Space (SL=L)
| SPECIAL SEMINAR | |
| Topic: | Undirected Graph Connectivity in Log-Space (SL=L) |
| Speaker: | Omer Reingold |
| Affiliation: | Weizmann Institute |
| Date: | Monday, February 28 |
| Time/Room: | 4:00pm - 5:00pm/S-101 |
We present a deterministic algorithm for graph connectivity that uses the minimal amount of memory possible, up to a constant factor. Specifically, the algorithm's memory is comparable to that needed to store only a single node of the graph (i.e., it is logarithmic in the size of the graph).
Our algorithm also implies a deterministic, short, universal sequence of steps which will get one out of every maze,
and through the streets of every city.
To obtain this algorithm, we give a method to transform (using small memory), an arbitrary connected graph into a sparse but highly connected graph (i.e., into an expander graph).
No special background is needed for this talk. Additional details on this work and on the results of a subsequent work will be given in a separate talk on Tuesday.