Authors
Oded Goldreich
Publication date
2019/1/27
Journal
Electronic Colloquium on Computational Complexity (ECCC)
Volume
26
Pages
12
Description
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 (ECCC, TR11–136, 2011). Pseudodeterministic algorithms are randomized algorithms that solve search problems by almost always providing the same canonical solution (per each input). Multi-pseudodeterministic algorithms relax the former notion by allowing the algorithms to output one of a bounded number of canonical solutions (per each input). We show that efficient multi-pseudodeterministic algorithms can solve natural problems that are not solveable by efficient pseudodeterministic algorithms, present a composition theorem regarding multi-pseudodeterministic algorithms, and relate them to other known notions.
Total citations
20192020202120222023202414461
Scholar articles
O Goldreich - Electronic Colloquium on Computational Complexity …, 2019