##
On the possibilities and limitations of pseudodeterministic algorithms

#### Webpage for a paper by Oded Goldreich, Shafi Goldwasser, and Dana Ron

#### Abstract

We study the possibilities and limitations of pseudodeterministic algorithms,
a notion put forward by Gat and Goldwasser (2011).
These are probabilistic algorithms that solve search problems
such that on each input, with high probability, they output
the same solution, which may be thought of as a canonical solution.
We consider both the standard setting of (probabilistic) polynomial-time
algorithms and the setting of (probabilistic) sublinear-time algorithms.
Some of our results are outlined next.

In the standard setting, we show that
pseudodeterminstic algorithms are more powerful
than deterministic algorithms if and only if $P \neq BPP$,
but are weaker than general probabilistic algorithms.
In the sublinear-time setting,
we show that if a search problem has a pseudodeterminstic algorithm
of query complexity $q$, then this problem can be solved deterministically
making $O(q^4)$ queries. This refers to total search problems.
In contrast, for several natural promise search problems,
we present pseudodeterministic algorithms that are much more efficient
than their deterministic counterparts.

#### Material available on-line

- First version posted:
Aug'12.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage
or general list of papers.