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. LIPIcs, Vol. 200, 36th Computational Complexity Conference (CCC 2021), pages 18:1-18:15