Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with ZPP:
TR12-101 | 10th August 2012
Oded Goldreich, Shafi Goldwasser, Dana Ron

On the possibilities and limitations of pseudodeterministic algorithms

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

TR20-059 | 16th April 2020
Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

Pr-ZSUBEXP is not contained in Pr-RP

Revisions: 1

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ... more >>>

ISSN 1433-8092 | Imprint