# 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