Back to search

University of Waterloo

Query Complexity of Recursively Composed Functions

Abstract

dc:description.abstract

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 \to \infty \sqrt[k]{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, \R0*(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*(\text{3-MAJ}) = R0*(\text{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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Al-Dhalaan, Bandar
Advisor dc:contributor.advisor
  • Ben-David, Shalev

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10012/21156

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Al-Dhalaan, Bandar. Query Complexity of Recursively Composed Functions. University of Waterloo, 2024. https://hdl.handle.net/10012/21156