A randomized time-space tradeoff of O˜(mRˆ) for USTCON

We present a randomized time space tradeoff of O˜(mRˆ) for undirected S-T-connectivity, where Rˆ Σ_υεV 1/d_υ is the virtual resistance of the graph. This solves an open question of Broder et al. (1989) (implicit also in Aleliunas et al. (1979)) who asked whether a tradeoff of O˜(mn) is achievable, and also improves upon a tradeoff of O˜(mn/d_min) conjectured by Barnes and Feige (1993). Our algorithm is a modification of the Broder et al. algorithm. In passing, we also improve a result from Barnes and Feige regarding the rate at which a random walk discovers new vertices in a graph