Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-024 | 15th February 2021 19:07

A Majority Lemma for Randomised Query Complexity

RSS-Feed




TR21-024
Authors: Mika Göös, Gilbert Maystre
Publication: 21st February 2021 12:18
Downloads: 1015
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint