BP(H)SPACE(S)subset of DSPACE(S-3/2)

We prove that any language that can be recognized by a randomized algorithm (with possibly a two-sided error) that runs in space O(S) and always termi nates can be recognized by deterministic algorithm running in space O(S-3/2 ). This improves the best previously known result that such algorithms have deterministic space O(S-2) simulations which, for one-sided error algorith ms, follows from Savitch's theorem and, for two-sided error algorithms, fol lows by reduction to recursive matrix powering. Our result includes as a sp ecial case the result due to Nisan, Szemeredi, and Wigderson that undirecte d connectivity can be computed in space O(log(3/2) n). It is Obtained via a new algorithm for repeated squaring of a matrix: we show how to approximat e the 2' th power of a d x d matrix in space O(r(1/2) log d), improving on the bound of O(r log d) that comes from the natural recursive algorithm. Th e algorithm employs Nisan's pseudorandom generator for space-bounded comput ation, together with some new techniques for reducing the number of random bits needed by an algorithm. (C) 1999 Academic Press.