All reports by Author Gilbert Maystre:

__
TR21-024
| 15th February 2021
__

Mika Göös, Gilbert Maystre#### A Majority Lemma for Randomised Query Complexity

Mika Göös, Gilbert Maystre

We show that computing the majority of $n$ copies of a boolean function $g$ has randomised query complexity $\mathrm{R}(\mathrm{Maj} \circ g^n) = \Theta(n\cdot \bar{\mathrm{R}}_{1/n}(g))$. In fact, we show that to obtain a similar result for any composed function $f\circ g^n$, it suffices to prove a sufficiently strong form of the ... more >>>