Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with mixing time:
TR05-022 | 19th February 2005
Omer Reingold, Luca Trevisan, Salil Vadhan

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

TR07-030 | 29th March 2007
Kai-Min Chung, Omer Reingold, Salil Vadhan

S-T Connectivity on Digraphs with a Known Stationary Distribution

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 ... more >>>

ISSN 1433-8092 | Imprint