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.