Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Pseudodeterministic algorithms:
TR19-012 | 27th January 2019
Oded Goldreich

Multi-pseudodeterministic algorithms

In this work, dedicated to Shafi Goldwasser, we consider a relaxation of the notion of pseudodeterministic algorithms, which was put forward by Gat and Goldwasser ({\em ECCC}, TR11--136, 2011).

Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). ... more >>>

TR21-039 | 15th March 2021
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic Algorithms and the Structure of Probabilistic Time

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>

ISSN 1433-8092 | Imprint