{"ID":6138257,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T13:31:09.21043372Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07396","arxiv_id":"2607.07396","title":"Gap-Majority Lemmas in Communication Complexity","abstract":"We prove an information-theoretically optimal \\emph{gap-majority lemma} in the two-player randomized communication model. For a base function $f: \\mathcal{X} \\to \\{\\pm 1\\}$, its $n$-fold \\emph{gap-majority composition}, denoted $\\mathsf{GapMAJ} \\circ f^n$, takes $n$ inputs $(X_1, \\ldots, X_n)$ and distinguishes whether $f^{+n}(X_1,\\ldots,X_n) := f(X_1) + \\ldots + f(X_n)$ is at least $0.01\\sqrt{n}$ or at most $-0.01\\sqrt{n}$. We show that if computing $f$ with success probability $0.501$ requires $I$ bits of information, then computing $\\mathsf{GapMAJ} \\circ f^n$ with success probability $0.99$ requires $n \\cdot (I - O(1))$ bits of information. This result is asymptotically optimal in two aspects: it achieves the correct linear scaling of information cost and the correct constant-constant tradeoff between error rates. This makes $\\mathsf{GapMAJ}$, to our knowledge, only the third explicit outer gadget that admits a strong composition theorem in the two-player communication setting, following the identity and XOR gadgets. From an application side, our gap-majority lemma can be viewed as a generic amplification tool that lifts the hardness of deciding $f$ into the hardness of approximating $f^{+n}$. Using this framework, we give a new proof to the communication lower bound of Gap-Hamming and derive a tight streaming lower bound of triangle counting, demonstrating the versatility of the gap-majority lemma.","short_abstract":"We prove an information-theoretically optimal \\emph{gap-majority lemma} in the two-player randomized communication model. For a base function $f: \\mathcal{X} \\to \\{\\pm 1\\}$, its $n$-fold \\emph{gap-majority composition}, denoted $\\mathsf{GapMAJ} \\circ f^n$, takes $n$ inputs $(X_1, \\ldots, X_n)$ and distinguishes whether...","url_abs":"https://arxiv.org/abs/2607.07396","url_pdf":"https://arxiv.org/pdf/2607.07396v1","authors":"[\"Pachara Sawettamalya\",\"Huacheng Yu\"]","published":"2026-07-08T13:32:29Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}