An Optimal Gap-Majority Lemma for Bounded Rounds Communication
En palabras de los autores
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.
Resultado principalLimitación que admiten los autores
Apareció: viernes, 16 de octubre. arXiv. Preprint, todavía sin revisión por pares.