Deterministic approximation of random walks in small space

DOI10.4086/TOC.2021.V017A004MaRDI QIDQ5158498zbMATH OpenOpenAlexFDO

Authors Jack Murtagh, Omer Reingold, Aaron Sidford, Salil Vadhan

Publication date 25 October 2021

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.06361

zbMATH Keywords

derandomizationexpander graphsrandom walksspace complexityspectral approximation

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 7650109
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Multiplicative Approximations of Random Walk Transition Probabilities
• Finding small sparse cuts by random walk
• A Chernoff Bound for Random Walks on Expander Graphs

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• An Elementary Construction of Constant-Degree Expanders
• Approximate maximum flow on separable undirected graphs
• Computational Complexity
• Computational Complexity
• Eigenvalues and expanders
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Explicit Concentrators from Generalized N-Gons
• Explicit constructions of linear-sized superconcentrators
• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 7650109 (Why is no real title available?)
• Log Depth Circuits for Division and Related Problems
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On Constructing Expanders for Any Number of Vertices
• Pseudorandom generators for regular branching programs
• Pseudorandomness for network algorithms
• Simple Constructions of Almost k-wise Independent Random Variables
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Spectral sparsification of graphs
• Undirected connectivity in log-space
• Uniform constant-depth threshold circuits for division and iterated multiplication.

Cited in

(6)

• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• On Constructing Expanders for Any Number of Vertices
• scientific article; zbMATH DE number 7650109 (Why is no real title available?)
• Expanderizing higher-order random walks
• Expanderizing higher-order random walks
• Toward derandomizing Markov chain Monte Carlo

This page was built for publication: Deterministic approximation of random walks in small space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158498)