Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Perfect Simulation of Las Vegas Algorithms via Local Computation


Jiang,  Yonggang
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 590KB

Supplementary Material (public)
There is no public supplementary material available

Fu, X., Jiang, Y., & Yin, Y. (2023). Perfect Simulation of Las Vegas Algorithms via Local Computation. Retrieved from https://arxiv.org/abs/2311.11679.

Cite as: https://hdl.handle.net/21.11116/0000-000F-147A-2
The notion of Las Vegas algorithm was introduced by Babai (1979) and may be
defined in two ways:
* In Babai's original definition, a randomized algorithm is called Las Vegas
if it has finitely bounded running time and certifiable random failure.
* Alternatively, in a widely accepted definition today, Las Vegas algorithms
mean the zero-error randomized algorithms with random running time.
The equivalence between the two definitions is straightforward. In
particular, by repeatedly running the algorithm until no failure encountered,
one can simulate the correct output of a successful running.
We show that this can also be achieved for distributed local computation.
Specifically, we show that in the LOCAL model, any Las Vegas algorithm that
terminates in finite time with locally certifiable failures, can be converted
to a zero-error Las Vegas algorithm, at a polylogarithmic cost in the time
complexity, such that the resulting algorithm perfectly simulates the output of
the original algorithm on the same instance conditioned on that the algorithm
successfully returns without failure.