Special Seminar

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.