Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-024 | 15th February 2021 19:07

#### A Majority Lemma for Randomised Query Complexity

TR21-024
Authors: Mika Göös, Gilbert Maystre
Publication: 21st February 2021 12:18
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 result only in the special case $g=\mathrm{GapOr}$.