Local Access to Random Walks

Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld

For a graph $G$ on $n$ vertices, naively sampling the position of a random walk of at time $t$ requires work $\Omega (t)$. We desire local access algorithms supporting $\text{position}(G…