Loading...
conference paper
A Majority Lemma for Randomised Query Complexity
Kabanets, Valentine
2021
[Proceedings of CCC 2021]
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
Loading...
Name
LIPIcs-CCC-2021-18.pdf
Type
publisher
Access type
openaccess
License Condition
CC BY
Size
735.15 KB
Format
Adobe PDF
Checksum (MD5)
232a02c4279c51c4e49658dc77b5306f