Derandomization of Euclidean Random Walks

DOI10.1007/978-3-540-74208-1_26zbMATH Open1171.68863OpenAlexW1582332289MaRDI QIDQ3603477FDOQ3603477

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

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

Mathematics Subject Classification ID

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

Cited In (8)

• Computable Carathéodory theory
• Computable complex analysis
• Computable Geometric Complex Analysis and Complex Dynamics
• Computability in harmonic analysis
• Computability of Brolin-Lyubich measure
• The rate of convergence of the walk on spheres algorithm
• EURANDOM: a decade of European stochastics
• Title not available (Why is that?)

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)