Pseudorandom walks on regular digraphs and the RL vs. L problem

DOI10.1145/1132516.1132583zbMath1301.05317OpenAlexW2131115830MaRDI QIDQ2931408

Omer Reingold, Luca Trevisan, Salil P. Vadhan

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132583

zbMATH Keywords

mixing timederandomizationexpander graphszig-zag productspace-bounded computationuniversal traversal sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)

Related Items

Equivalence classes and conditional hardness in massively parallel computations ⋮ Derandomized constructions of \(k\)-wise (almost) independent permutations ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Expander graphs and their applications ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ Nonlinear spectral calculus and super-expanders ⋮ Space Complexity of Reachability Testing in Labelled Graphs ⋮ Complexity classes of equivalence problems revisited ⋮ In a World of P=BPP ⋮ Space complexity of reachability testing in labelled graphs ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace