HOME / PUBLICATIONS /

S-T connectivity on digraphs with a known stationary distribution

Citation:

Chung, Kai-Min, Omer Reingold, and Salil Vadhan. “S-T connectivity on digraphs with a known stationary distribution.” In ACM Transactions on Algorithms. Vol. 7. 3rd ed. ACM, 2011.
ECCC2007.pdf263 KB
ACM2011.pdf223 KB

Abstract:

Version history: Preliminary versions in CCC '07 and on ECCC (TR07-030).

We present a deterministic logspace algorithm for solving S-T Connectivity on directed graphs if: (i) we are given a stationary distribution of the random walk on the graph in which both of the input vertices \(s\) and \(t\) have nonnegligible probability mass 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 [Reingold, 2008]. 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).

 

Publisher's Version

See also: Computational Complexity, Pseudorandomness, A Unified Theory of Pseudorandomness (NSF CCF-0133096), Pseudorandomness and Applications (ONR Young Investigator Award; ONR Grant N00014-04-1-0478), Pseudorandomness and Combinatorial Constructions (US-Israel Binational Science Foundation; BSF 2002246)
Last updated on 07/15/2020