Oded Goldreich, Shafi Goldwasser, Dana Ron

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 ...
more >>>