When Connectivity Is Hard, Random Walks Are Easy with Non-determinism.

Dean Doron, Edward Pyne, Roei Tell, R. Ryan Williams

Browse the full STOC paper archive.