TR21-024 Authors: Mika Göös, Gilbert Maystre

Publication: 21st February 2021 12:18

Downloads: 721

Keywords:

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}$.