DIMACS Discrete Math/Theory of Computing Seminar


Undirected s,t-connectivity is in DSPACE(log^{4/3} n)


Shiyu Zhou
Bell Laboratories


DIMACS Center, CoRE Building, Seminar Room 431
Rutgers University


4:30 PM
Tuesday, February 4, 1997

The (s,t) connectivity problem is: given as input an undirected graph and two vertices s and t, determine whether there is a path >from s to t. A major open question in complexity is whether this problem can be solved in space logarithmic in n, the number of vertices. We present a deterministic algorithm that solves this using O(log^{4/3} n) space. This improves the previous O(log^{3/2} n) space algorithm of Nisan, Szemeredi and Wigderson.

This is joint work with Roy Armoni, Amnon Ta-Shma, and Avi Wigderson.

Document last modified on January 30, 1997