scientific article; zbMATH DE number 7650109

DOI10.4230/LIPICS.APPROX-RANDOM.2019.42MaRDI QIDQ5875498zbMATH OpenFDO

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

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.42

zbMATH Keywords

random walksderandomizationexpander graphsspace complexityspectral approximation

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• Deterministic approximation of random walks in small space
• Deterministic random walks on finite graphs
• Deterministic random walks on finite graphs
• Random walks strictly confined to a subspace
• Deterministic random walks
• scientific article; zbMATH DE number 2247483
• Deterministic walks in random environments
• Deterministically driven random walks on a finite state space
• scientific article; zbMATH DE number 5763161

Cites work

• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• A framework for analyzing resparsification algorithms
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• An efficient parallel solver for SDD linear systems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Density independent algorithms for sparsifying k-step random walks
• Explicit constructions of linear-sized superconcentrators
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• 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
• Undirected connectivity in log-space
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)

Cited in

(8)

• Explicit expanders of every degree and size
• Small-space spectral sparsification via bounded-independence sampling
• Pseudorandom generators for unbounded-width permutation branching programs
• Deterministic approximation of random walks in small space
• Spectral sparsification via bounded-independence sampling
• Derandomization with pseudorandomness
• Near-optimal derandomization of medium-width branching programs
• Nearly optimal pseudorandomness from hardness

This page was built for publication:

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