Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-112 | 12th August 2022 22:24

Randomised Composition and Small-Bias Minimax


Authors: Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Publication: 12th August 2022 22:53
Downloads: 116


We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, $\mathrm{LR}$ can be polynomially larger than previous measures that satisfy an inner composition theorem, such as the max-conflict complexity of Gavinsky, Lee, Santha, and Sanyal (ICALP 2019).

Our second result addresses a question of Yao (FOCS 1977). He asked if $\epsilon$-error expected query complexity $\bar{\mathrm{R}}_\epsilon(f)$ admits a distributional characterisation relative to some hard input distribution. Vereshchagin (TCS 1998) answered this question affirmatively in the bounded-error case. We show that an analogous theorem fails in the small-bias case $\epsilon=1/2-o(1)$.

ISSN 1433-8092 | Imprint