CS Paper Radar

Weak Composition Theorems for Randomized Communication

Pachara Sawettamalya

cs.CC ·submitted 2026-11-12 02:31 UTC · v1
theory

Abstract

We present two results towards the randomized communication complexity of composed functions. Our contributions include: - \textbf{Lifting-by-Influence.} For any binary function $f$ and any outer gadget $g:\{0,1\}^n \rightarrow \mathbb{R}$, we show that up to additive terms, computing $g \circ f^n$ information-theoretically requires solving at least $\operatorname{Inf}(g)$ instances of $f$, where $\operatorname{Inf}(g)$ denotes the total influence of $g$. To our knowledge, this is the first composition lower bound for randomized communication that applies to \emph{every} choice of $f$ and $g$. - \textbf{Symmetric Composition.} When $g$ is a symmetric function with a value transition at Hamming weight $d$, we strengthen the number of required instances to $\min\{d,n+1-d\}$. As an implication, this recovers the previously known direct-sum theorem, XOR lemma, and majority lemma. Our proofs develop novel and distinctive usages of the classical \emph{input embedding} argument of Barak, Braverman, Chen, and Rao (SICOMP 2013). As an additional ingredient, we introduce a new public sampling framework that avoids auxiliary communication during the recovery phase of the protocol, ultimately reducing the extra cost from $O(n)$ bits of information to just $O(1)$.

Closest papers

Nearest neighbours by meaning across the whole index.

An Optimal Gap-Majority Lemma for Bounded-Round Communication

cs.CC ·2026-10-15 ·Pachara Sawettamalya
similarity 0.74
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 whether $\sum_{i=1}^n f(X_i,Y_i)$ is at least $0.01\sqrt{n}$ or at most $-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 show that a minor adaptation of their approach, together with a more refined analysis, achieves the conjectured $O(1)$ loss, establishing a gap-majority lemma for bounded-round communication that is optimal up to constant factors.

0.25

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.72
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46

Randomized Lifting for One-Way Number-on-Forehead Communication

cs.CC ·2026-09-26 ·Chenyu Wang
theory similarity 0.69
Abstract

We prove a lifting theorem from two-party public-coin one-way communication to multiparty public-coin one-way number-on-forehead (NOF) communication. For every fixed $k\ge2$ and prime $q>2k$, there is a generalized inner product gadget $\GIP_{q,r}^k:(\F_q^r)^k\to\F_q$ with $r=O_k(q/\log q)$ such that, for every partial Boolean function $f:D\to\bits$, where $D\subseteq\F_q\times\F_q$, \[ R_{1/3}^1(f)-O(1) \le R_{1/6}^{1,\NOF}\bigl(f\circ\GIP_{q,r}^k\bigr) \le R_{1/6}^1(f). \] Thus, composition with the gadget preserves one-way randomized communication complexity up to an additive constant and a change in the error parameter. The lower bound holds in the general one-way NOF model, where the last player sees the entire gadget input. This extends the deterministic one-way NOF lifting theorem of Yang and Zhang to randomized protocols, and extends the randomized lifting result of Wang and Wu from the conservative model to the general one-way NOF model. Our proof introduces a one-way cylinder partition bound that lower bounds public-coin one-way NOF communication complexity. We show that, for the lifted function, this bound is at least half the one-way partition bound of the outer function. The main technical step transfers a dual solution between the two bounds, using Möbius inversion and a discrepancy estimate for generalized inner product to control the loss. Combining this transfer with the characterization of two-party one-way randomized communication complexity by the one-way partition bound yields the lifting theorem.

0.29

Capacity regimes for Boolean function computation via channels

cs.IT ·2026-08-11 ·Jingge Zhu, Matthias Frey
similarity 0.69
Abstract · A part of this work has been reported in https://arxiv.org/pdf/2601.12640

Consider a point-to-point communication system in which the transmitter holds a binary message of length $m$ and transmits a corresponding codeword of length $n$. The receiver's goal is to recover a Boolean function of that message, where the function is unknown to the transmitter, but chosen from a known class $F$. We are interested in the asymptotic relationship of $m$ and $n$: given $n$, how large can $m$ be (asymptotically), such that the value of the Boolean function can be recovered reliably? This problem generalizes the identification-via-channels framework introduced by Ahlswede and Dueck. In this paper, we formulate the notion of computation capacity, and derive achievability and converse results for a large class of functions $F$, characterized by the Hamming weight of functions. Different from the classical transmission problem, the performance of the function computation problem is jointly characterized by the computation capacity and the rate function, namely how $m$ scales with $n$ asymptotically. Our results give a complete characterization of the rate function of the computation problem, and provide upper and lower bounds on the computation capacity, where they differ by a factor of at most $2$.

0.52

Composition Theorem for Randomized Query Complexity

cs.CC ·2026-11-05 ·Samruddhi Pednekar, Supartha Podder
theory similarity 0.66
Abstract · 21 pages

For bounded-error randomized query complexity, we resolve the composition conjecture up to logarithmic factors. The general upper bound $R(f\circ g) = O\!\left(R(f)R(g)\log(R(f)+1)\right)$ was already known. Although Meiburg recently disproved constant-factor multiplicative composition for total Boolean functions, the conjecture allowing polylogarithmic losses remained open. We settle this question by proving that, for all (possibly partial) Boolean functions $f$ and $g$, \[ R(f\circ g) = Ω\!\left(\frac{R(f)R(g)}{\log(n+1)}\right), \] where $n$ is the input size for $f$.

0.14

No Perfect Randomized Composition

cs.CC math.CO ·2026-10-22 ·Alexander Meiburg
similarity 0.66
Abstract · 56 pages

Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =Θ\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$, from standard randomized query complexity $R$. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$, max-conflict $\barχ$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$. The total--total composition separation is also formalized in Lean.

0.48

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

cs.CR cs.CC ·2026-10-15 ·Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior
theory similarity 0.66
Abstract

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output without learning anything else about the inputs. Perfect privacy requires identical transcript distributions on inputs with the same output. We also study the weaker notion of support privacy, which requires only that these distributions have the same support. We study the communication complexity of symmetric Boolean functions when each of the $n$ parties holds one input bit. Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing $OR_n$. Our technique gives $Ω(n\log n)$ lower bounds for $MAJ_n$ and $EMAJ_n$ (with even $n$), and an $Ω(n\log q)$ lower bound for $MOD_q$ when $q\leq(1-c)n$ for a fixed constant $c>0$. Upper bounds. We construct perfectly private PSM protocols of total communication $\widetilde{O}(n^{3/2})$ for every symmetric Boolean function, improving on the known quadratic bound. For $MAJ_n$, known branching-program constructions yield an upper bound of $O(n\log^3 n\log\log n)$. For $EMAJ_n$ and $MOD_q$ with prime $q$, the lower bounds are tight up to constant factors in the stated regimes. Under support privacy, we obtain $\widetilde{O}(n)$ communication for every symmetric Boolean function. Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions. Concurrent and independent work by Holmgren and Wu proves a $ω(n)$ lower bound for $OR_n$ using the same combinatorial core. Both works used AI assistance.

0.14

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.65
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16