ECCC-Report TR07-030https://eccc.weizmann.ac.il/report/2007/030Comments and Revisions published for TR07-030en-usThu, 29 Mar 2007 07:35:36 +0200
Paper TR07-030
| S-T Connectivity on Digraphs with a Known Stationary Distribution |
Kai-Min Chung,
Omer Reingold,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2007/030We 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$).
Thu, 29 Mar 2007 07:35:36 +0200https://eccc.weizmann.ac.il/report/2007/030