Optimal communication limits for bounded round majority problems
An Optimal Gap-Majority Lemma for Bounded Rounds Communication
Computational Complexity
Summary
Figuring out the total result of many small yes/no decisions is a common problem in computer communication. The paper improves understanding of how much information must be exchanged to reliably tell if the total sum of many small outcomes is mostly positive or mostly negative, using a method with limited back-and-forth communication. The authors build on earlier work and show the smallest possible extra cost in communication beyond a known baseline. This helps clarify fundamental communication limits in distributed computing and data processing.
What this means in practice
- •For distributed system designers: Guide the design of communication protocols with optimal information cost for bounded-round computation of majority-like functions.
- •For data processing engineers: Inform bandwidth requirements when implementing efficient consensus or aggregation procedures in systems with limited communication rounds.
A theory result. No direct application yet.
Authors
Pachara Sawettamalya
Abstract
Recent work of Sawettamalya and Yu (FOCS 2026) initiated the study of \emph{gap-majority} composition in randomized communication. They showed that if computing a $\{\pm 1\}$-valued function $f$ in $r$ rounds requires $I$ bits of information, then distinguishing $\sum_{i=1}^n f(X_i,Y_i)\geq 0.01\sqrt{n}$ from $\sum_{i=1}^n f(X_i,Y_i)\leq -0.01\sqrt{n}$ in $r$ rounds requires $n \cdot (I-O(\log n))$ bits of information. They also conjectured that the $O(\log n)$-additive ``loss'' can be further reduced to $O(1)$. In this note, we record that a minor adaptation to their approach combining with a finer analysis achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.