Master’s Thesis Presentation • Algorithms and Complexity • Variants of Pseudo-deterministic Algorithms and Duality in TFNP

Please note: This master’s thesis presentation will take place in DC 3317 and online.

Mohammad Hossein Ebtehaj, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Shalev Ben-David

We introduce a new notion of “faux-deterministic” algorithms for search problems in query complexity. Roughly, for a search problem $\cS$, a faux-deterministic algorithm is a probability distribution $\mathcal{A}$ over deterministic algorithms such that no computationally bounded adversary making black-box query to an algorithm $A\sim \mathcal{A}$ can find an input on which it fails to solve $\cS$. Faux-deterministic algorithms are a relaxation of pseudo-deterministic algorithms, which are randomized algorithms with the guarantee that for any given input $x$, the algorithm outputs a unique output $y_x$ with high probability.

Pseudo-deterministic algorithms are statistically indistinguishable from deterministic algorithms, while faux-deterministic algorithms relax the statistical indistinguishability to computational indistinguishability.

We prove that in the query model, every verifiable search problem with a randomized algorithm also has a faux-deterministic algorithm. This immediately proves an exponential gap between pseudo-deterministic and faux-deterministic complexities in query complexity. We additionally show that our faux-deterministic algorithm is also secure against quantum adversaries that can make black-box queries in superposition.

We highlight two reasons to study faux-deterministic algorithms. First, for practical purposes, one can use a faux-deterministic algorithm instead of pseudo-deterministic algorithms in most cases where the latter is required. Second, since efficient faux-deterministic algorithms exist even when pseudo-deterministic ones do not, their existence demonstrates a barrier for proving pseudo-deterministic lower bounds: lower bounds on pseudo-determinism must distinguish pseudo-determinism from faux-determinism.

Finally, changing our perspective to adversaries’ viewpoint, we introduce the notion of a dual problem for search problems $\cS$. In the dual problem $\cS^*$, the input is an algorithm $A$ purporting to solve $\cS$, and our goal is to find an adverse input $x$ on which $A$ fails to solve $\cS$. We discuss several properties in the query and Turing machine model that show the new problem $\cS^*$ is analogous to a dual for $\cS$.

To attend this master’s thesis presentation in person, please go to DC 3317. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/my/mhebtehaj.