Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PSEUDODETERMINISTIC ALGORITHMS:
Reports tagged with Pseudodeterministic algorithms:
TR19-012 | 27th January 2019
Oded Goldreich

#### Multi-pseudodeterministic algorithms

Revisions: 1

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