Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
When Is Amplification Necessary for Composition in Randomized Query Complexity? , booktitle =
1 Pith paper cite this work, alongside 6 external citations. Polarity classification is still indexing.
1
Pith paper citing it
6
external citations · OpenAlex
fields
cs.CC 1years
2026 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Gap-Majority Lemmas in Communication Complexity
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.