Papers for

data processing engineers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Optimal communication limits for bounded round majority problems

An Optimal Gap-Majority Lemma for Bounded Rounds Communication

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.

Thu 15 OctComputational Complexity
The gist
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.
Open → 2610.22313v1