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.