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

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the ... more >>>

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>