ECCC-Report TR19-012https://eccc.weizmann.ac.il/report/2019/012Comments and Revisions published for TR19-012en-usMon, 04 Oct 2021 16:00:10 +0300
Revision 1
| Multi-pseudodeterministic algorithms |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2019/012#revision1In 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).
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-seudodeterministic 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.
Mon, 04 Oct 2021 16:00:10 +0300https://eccc.weizmann.ac.il/report/2019/012#revision1
Paper TR19-012
| Multi-pseudodeterministic algorithms |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2019/012In 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).
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-seudodeterministic 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.
Sun, 27 Jan 2019 19:25:14 +0200https://eccc.weizmann.ac.il/report/2019/012