Pseudo-deterministic Algorithms (Invited Talk)

Author Shafi Goldwasser



PDF
Thumbnail PDF

File

LIPIcs.STACS.2012.29.pdf
  • Filesize: 383 kB
  • 1 pages

Document Identifiers

Author Details

Shafi Goldwasser

Cite AsGet BibTex

Shafi Goldwasser. Pseudo-deterministic Algorithms (Invited Talk). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, p. 29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.29

Abstract

In this talk we describe a new type of probabilistic algorithm which we call "Bellagio" Algorithms: a randomized algorithm which is guaranteed to run in expected polynomial time, and to produce a correct and unique solution with high probability. These algorithms are pseudo-deterministic: they can not be distinguished from deterministic algorithms in polynomial time by a probabilistic polynomial time observer with black box access to the algorithm. We show a necessary and sufficient condition for the existence of a Bellagio Algorithm for an NP relation R: R has a Bellagio algorithm if and only if it is deterministically reducible to some decision problem in BPP. Several examples of Bellagio algorithms, for well known problems in algebra and graph theory which improve on deterministic solutions, follow. The notion of pseudo-deterministic algorithms (or more generally computations) is interesting beyond just sequential algorithms. In particular, it has long been known that it is impossible to solve deterministically tasks such as "consensus" in a faulty distributed systems, whereas randomized protocols can achieve consensus in expected constant time. We thus explore the notion of pseudo-deterministic fault tolerant distributed protocols: randomized protocols which are polynomial time indistinguishable from deterministic protocols in presence of faults.
Keywords
  • randomized algorithms
  • distributed computing
  • Monte Carlo
  • Las Vegas

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail