Derandomization of euclidean random walks

Ilia Binder, Mark Braverman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We consider the problem of derandomizing random walks in the Euclidean space ℝk. We show that for k = 2, and in some cases in higher dimensions, such walks can be simulated in Logspace using only poly-logarithmically many truly random bits. As a corollary, we show that the Dirichlet Problem can be deterministically simulated in space O(log n √log log n), where 1/n is the desired precision of the simulation.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings
PublisherSpringer Verlag
Pages353-365
Number of pages13
ISBN (Print)9783540742074
DOIs
StatePublished - 2007
Externally publishedYes
Event10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007 - Princeton, NJ, United States
Duration: Aug 20 2007Aug 22 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4627 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2007 and 11th International Workshop on Randomization and Computation, RANDOM 2007
CountryUnited States
CityPrinceton, NJ
Period8/20/078/22/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Derandomization of euclidean random walks'. Together they form a unique fingerprint.

  • Cite this

    Binder, I., & Braverman, M. (2007). Derandomization of euclidean random walks. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 10th International Workshop, APPROX 2007 and 11th International Workshop, RANDOM 2007, Proceedings (pp. 353-365). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4627 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-74208-1_26