CS Paper Radar

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

Chenyu Wang

cs.CC ·submitted 2026-09-26 12:20 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Weak Composition Theorems for Randomized Communication

cs.CC ·2026-11-12 ·Pachara Sawettamalya
theory similarity 0.69
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)$.

0.06

Composition Theorem for Randomized Query Complexity

cs.CC ·2026-11-05 ·Samruddhi Pednekar, Supartha Podder
theory similarity 0.62
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

Target-Dependent Local Verification: Information--Proof-Length Tradeoffs

cs.CC ·2026-08-22 ·Hongmin Li
theory similarity 0.62
Abstract · 15 pages. Submitted to computational complexity

We study fixed-layout local verification with target-dependent local tests. Let $M$ be a random variable on $\{0,1\}^K$, and let $S$ record the test selected at each coordinate. For each $s\in\operatorname{supp}(S)$, let $F_s$ be the corresponding target fiber and set $D_{\mathrm{fib}}=\max_s\operatorname{VCdim}(F_s)$. We prove $H(M\mid S)\le \log_2\!\left(\sum_{j=0}^{D_{\mathrm{fib}}}\binom Kj\right)$. A fiber that shatters $d$ coordinates yields a weak relaxed locally decodable code with message length $d$ and block length $d+P$ over the original proof alphabet. For a uniform $K$-bit target and fixed proof alphabet, $Q$, and $σ$, the Goldberg--Gur--Saraogi lower bound implies that $I(M;S)\leγK$, for fixed $γ<1$, forces $P=Ω\!\left(K^{1+1/a}/(\log K)^{2+2/a}\right)$, where $a=\lceil Q/σ\rceil$. If $P\le K(\log K)^c$, then $I(M;S)\ge K-O\!\left(K^{a/(a+1)}(\log K)^{3+ac/(a+1)}\right)=K-o(K)$. Any discrete verifier state $T$ determining $S$ satisfies the same information lower bound. Bounded-randomness adaptive branches can be simulated nonadaptively by exposing their decision trees. A branch using at most $r$ random bits and $q$ adaptive proof queries yields a decoder with perfect completeness and at most $1+2^{r+1}\sum_{j<q}A^j$ queries. Under $I(M;S)\leγK$, near-linear proof length requires this quantity to be $Ω(\log K/\log\log K)$; the binary one-query case gives $P=2^{Ω(K)}$. Applied to a global list-sound dPCP interface of Gur--Minzer--Weissenberg--Zheng, our bound shows that a fixed target-independent menu of $L$ test profiles must satisfy $\log_2L\ge K-o(K)$. Proof-dependent lists and additional target-dependent selection data must be included in the measured state.

0.32

Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings

cs.CC quant-phcond-mat.str-elcs.IT ·2026-08-19 ·Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun
theory similarity 0.62
Abstract · 33 pages, 2 figures, 1 table

Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spreading logical information through simple gates applied in parallel. Brown and Fawzi showed that random Clifford circuits on two-qubit Clifford gates provide such encoders that achieve the quantum Gilbert-Varshamov rate-distance tradeoff with depth $O(\log^3 n)$. We show that the same asymptotic tradeoff is attained in optimal $O(\log n)$ depth under a gate distribution with a more restricted support. For every fixed $δ>0$ and sufficiently large $n$, if $\frac kn < 1 - H(\frac{d}{n}) - \frac{d}{n}\log_2 3 - δ$, we can construct random circuits of depth $O(\log n)$ which define, with high probability, an $[n,k]$ stabilizer code of distance at least $d+1$, which matches the $Ω(\log n)$ light-cone lower bound for linear distance encoders. Our ensemble employs a random matching circuit architecture consisting of $T$ independent permutation-invariant layers. In each layer, the qubits are paired up by a uniformly random perfect matching, and a random independent two-qubit Clifford gate is applied to each pair. The gate distribution need not be uniform over, or even have full support on, the two-qubit Clifford group; rather, we allow for very general distributions on Clifford gates satisfying three regularity conditions. In particular, the construction can be implemented using $n/2$ CNOT gates on randomly matched pairs in each layer, with parallel one-qubit Clifford twirls. These regularity conditions allow us to reduce the second-moment dynamics of our random circuits to a reversible Markov chain on binary support strings. We establish logarithmic hitting-time bounds for this Markov chain and comparisons of its stationary distribution to prove the coding properties of the circuits.

0.38

An Optimal Gap-Majority Lemma for Bounded-Round Communication

cs.CC ·2026-10-15 ·Pachara Sawettamalya
similarity 0.62
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

Exponential Quantum Advantage in Numbers-on-Forehead Communication

cs.CC quant-ph ·2026-09-30 ·Haoyu Wang, Pei Wu, Guangxu Yang
publishedtheory similarity 0.62
Abstract · 27 pages. Minor editorial revisions

We give the first exponential quantum advantage in the general interactive three-party Numbers-on-Forehead (NOF) model for a decision problem. Previous separations hold only for restricted protocols like one-way communication for a relation. We construct an explicit partial Boolean function, the Interleaved Unitary Product problem, that requires only $O(\log n)$ NOF quantum communication but $\widetildeΩ(n^{1/32})$ randomized communication. This function builds on the two-party unitary product problem of Arunachalam, Girish, and Lifshitz (TQC 2024). The main technical obstacle is that discrepancy, the standard lower-bound method for NOF, also lower-bounds quantum communication. We instead develop a regularity-based argument for randomized NOF lower bounds, building on the approach of Kelley, Lovett, and Meka and adapting the regularity decomposition of Abboud, Fischer, Kelley, Lovett, and Meka (STOC 2024) to cylinder intersections. Combined with matrix-product estimates of Arunachalam, Girish, and Lifshitz, this yields our randomized lower bound.

0.58

Separations Between Randomized and Exact Quantum Query Complexity for Boolean Functions

cs.CC quant-ph ·2026-11-16 ·Zekun Ye
similarity 0.62
Abstract

We construct a family of total Boolean functions $F_{\mathrm{tot}}$ whose randomized and exact quantum query complexities satisfy $R(F_{\mathrm{tot}}) \ge Q_E(F_{\mathrm{tot}})^{2-o(1)}$. Chiruvella, Kayal, Mittal, Paraashar, and Saurabh (2026) also obtained a nearly quadratic separation for total functions in the query model by a different method. For every fixed $\varepsilon \in (0,1)$, we construct a family of partial Boolean functions $F_{\mathrm{par}}$ on $n$ bits satisfying $Q_E(F_{\mathrm{par}})=O_\varepsilon(1)$ and $R(F_{\mathrm{par}})=Ω_\varepsilon(n^{1-\varepsilon})$. This matches the asymptotic separation previously obtained with bounded error (STOC 2021; SICOMP 2023). Lifting yields a family of partial communication functions $G_{\mathrm{par}}$ with $Q_E^{\mathrm{cc}}(G_{\mathrm{par}})=O_\varepsilon(\log n)$ and $R^{\mathrm{pub,cc}}(G_{\mathrm{par}})=Ω_\varepsilon(n^{1-\varepsilon})$, where $n$ is the total number of input bits held by the two parties.

0.13

On the Limits of Quantum Multiparty Simultaneous Communication

cs.CC quant-ph ·2026-09-09 ·Pedro Montealegre, Ivan Rapaport, Jorge Valenzuela
theory similarity 0.62
Abstract · 27 pages, 1 figure

We study the relative power of public randomness and quantum communication in the multiparty Simultaneous Message Passing (SMP) model. By analyzing a total Boolean function and a relational problem, we establish polynomial and exponential separations between classical public-coin protocols and quantum protocols without shared randomness or prior entanglement. We first introduce XOR Equality, a total Boolean function in which each of $k$ players receives an unrestricted string $x_j\in\{0,1\}^n$, and the referee must decide whether $x_1\oplus\cdots\oplus x_k=0^n$. For $k\ge8$ and worst-case error at most $1/3$, we prove quantum lower bounds of $Ω(\min\{n,k^2\})$ on total communication and $Ω(\min\{n/k,k\})$ on maximum message length. A classical public-coin protocol uses two bits per player with error at most $1/4$. For $n=k^2$ and worst-case error at most $1/3$, we prove that quantum protocols require maximum message length $Ω(\sqrt n)$ qubits, whereas two public-coin bits per player suffice. We then turn to relations, for which we obtain exponential separations. Specifically, we study Multiparty Index Coordination, a $k$-player generalization of the two-player relation studied by Gavinsky, Kempe, Regev, and de Wolf (STOC 2006). We prove an unambiguous quantum lower bound of $Ω(n^{1-1/k})$ on maximum message length, matched by a classical private-coin protocol. For any fixed error $\varepsilon\in(0,1/8)$, we also prove a bounded-error quantum lower bound of $Ω(n^{(k-1)/(k+1)})$ while we show that public-coin protocols solve the relation unambiguously with maximum message length $O(\log n)$, giving exponential separations in both regimes. The implicit constants are independent of $k$, and both quantum lower bounds become linear when $k\ge c\log n$ for any fixed $c>0$.

0.25