RSPACE(S)⊆DSPACE(S3/2)

We prove that any language that can be recognized by a randomized algorithm (with possibly two-sided error) that runs in space S and expected time 2^0(s) can be recognized by a deterministic algorithm running in space S^3/2. This improves over the best previously known result that such algorithms have deterministic space S ² simulations which, for one-sided error algorithms, follows from Savitch´s Theorem and for two-sided error algorithms follows by reduction to recursive matrix powering. Our result includes as a special case the result due to N. Nisan et al. (1992), that undirected connectivity can be computed in space log^3/2n. It is obtained via a new algorithm for repeated squaring of a matrix we show how to approximate the 2^τ power of a d×d matrix in space τ^1/2 log d, improving on the bo und of τ log d that comes from the natural recursive algorithm. The algorithm employs Nisan´s pseudorandom generator for space bounded computation, together with some new techniques for reducing the number of random bits needed by an algorithm