A Majority Lemma for Randomised Query Complexity

We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅1/n(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently strong form of the result only in the special case g = GapOr.