Randomised Composition and Small-Bias Minimax

Shalev Ben-David, Eric Blais, Mika Göös +1

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-opti…