DIMACS Discrete Math/Theory of Computing Seminar


Title:

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

Speaker:

Shiyu Zhou
Bell Laboratories

Place:

DIMACS Center, CoRE Building, Seminar Room 431
Rutgers University

Time:

4:30 PM
Tuesday, February 4, 1997
Abstract:

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