pipette
ESEspañol

An Optimal Gap-Majority Lemma for Bounded Rounds Communication

Pachara Sawettamalya

Preprint

In the authors' words

Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of gap-majority composition in randomized communication. They showed that if computing a -valued function in rounds requires bits of information, then distinguishing from in rounds requires bits of information. They also conjectured that the -additive "loss" can be further reduced to . In this note, we record that a minor adaptation to their approach combining with a finer analysis achieves the conjectured loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.

Main resultLimitation the authors admit

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.