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