ECCC-Report TR22-112https://eccc.weizmann.ac.il/report/2022/112Comments and Revisions published for TR22-112en-usFri, 12 Aug 2022 22:53:38 +0300
Paper TR22-112
| Randomised Composition and Small-Bias Minimax |
Shalev Ben-David,
Eric Blais,
Mika Göös,
Gilbert Maystre
https://eccc.weizmann.ac.il/report/2022/112We 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)$.Fri, 12 Aug 2022 22:53:38 +0300https://eccc.weizmann.ac.il/report/2022/112