Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-112 | 12th August 2022 22:24

Randomised Composition and Small-Bias Minimax

RSS-Feed




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


Abstract:

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