Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-030 | 29th March 2007 00:00

S-T Connectivity on Digraphs with a Known Stationary Distribution

RSS-Feed




TR07-030
Authors: Kai-Min Chung, Omer Reingold, Salil Vadhan
Publication: 29th March 2007 07:35
Downloads: 1401
Keywords: 


Abstract:

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace algorithm for s-t connectivity on undirected graphs (ECCC TR 04-94). It identifies knowledge of the stationary distribution as the gap between the s-t connectivity problems we know how to solve in logspace ($\L$) and those that capture all of randomized logspace ($\RL$).



ISSN 1433-8092 | Imprint