License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.29
URN: urn:nbn:de:0030-drops-34435
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3443/
Go to the corresponding LIPIcs Volume Portal

Goldwasser, Shafi

Pseudo-deterministic Algorithms (Invited Talk)

pdf-format:
59.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{goldwasser:LIPIcs:2012:3443,
  author =	{Shafi Goldwasser},
  title =	{{Pseudo-deterministic Algorithms (Invited Talk)}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{29--29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{Christoph D{\"u}rr and Thomas Wilke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3443},
  URN =		{urn:nbn:de:0030-drops-34435},
  doi =		{10.4230/LIPIcs.STACS.2012.29},
  annote =	{Keywords: randomized algorithms, distributed computing, Monte Carlo, Las Vegas}
}

Keywords: randomized algorithms, distributed computing, Monte Carlo, Las Vegas
Collection: 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Issue Date: 2012
Date of publication: 24.02.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI