Please note: This master’s thesis presentation will take place online.
Bandar Al-Dhalaan, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Shalev Ben-David
In this work, we explore two well-studied notions of randomized query complexity; bounded-error randomized (R(f)), and zero-error randomized (R0(f)). These have their natural analogues from the classical model of computation, R corresponding to BPP or “Monte Carlo” algorithms and R0 to ZPP or “Las Vegas” algorithms.
For a query complexity measure M, one can define the composition limit of M on f by M∗(f) = limk→∞ pk M(fk). The composition limit is a useful way to understand the asymptotic complexity of a function with respect to a specific measure (e.g. if M(f) = O(1)M(g), then M∗(f) = M∗(g)).
We show that under the composition limit, Las Vegas algorithms can be reduced to Monte Carlo algorithms in the query complexity world. Specifically, R∗0(f)=max(C∗(f),R∗(f)) for all possibly-partial boolean functions f. This has wide-reaching implications for the classical query complexity of boolean functions that are still open. For example, this result implies that any bounded-error algorithm for recursive 3-majority can be converted into a zero-error algorithm with no additional cost (i.e. R∗(3-MAJ) = R0∗(3-MAJ).
Furthermore, we explore one possible generalization of the recursive 3-majority problem itself, by analyzing 3-majority as a special case of a combinatorial game we call Denial Nim.
You can attend this presentation on Zoom.