Derandomization of Euclidean Random Walks

DOI10.1007/978-3-540-74208-1_26MaRDI QIDQ3603477zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Ilia Binder

Publication date 17 February 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74208-1_26

Mathematics Subject Classification ID

Randomized algorithms (68W20) Sums of independent random variables; random walks (60G50) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Pseudorandom walks on regular digraphs and the RL vs. L problem
• Randomness is linear in space
• \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
• Derandomizing isolation in space-bounded settings
• There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator

Cited in

(8)

• Computability in harmonic analysis
• Computable Carathéodory theory
• Computable complex analysis
• The rate of convergence of the walk on spheres algorithm
• scientific article; zbMATH DE number 922958 (Why is no real title available?)
• Computable Geometric Complex Analysis and Complex Dynamics
• Computability of Brolin-Lyubich measure
• EURANDOM: a decade of European stochastics

This page was built for publication: Derandomization of Euclidean Random Walks

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