Randomized communication complexity lifted from two to many parties
Randomized Lifting for One-Way Number-on-Forehead Communication
Computational Complexity
Summary
This paper studies how a communication problem involving two players can be transformed into a version involving many players while preserving the difficulty of solving it with randomization. The authors show that a special gadget function can be used to convert a two-person communication problem into a multi-person one without changing how hard it is to solve in a one-way communication setting. This extends previous results that only covered deterministic or more restricted cases. Their approach includes a new mathematical bound that helps prove this equivalence.
What this means in practice
- •For distributed system designers: Understand communication cost lower bounds when scaling from two-party to multiparty one-way protocols.
- •For cryptographic protocol developers: Employ communication complexity insights to analyze security and efficiency in multi-party protocols with limited communication.
A theory result. No direct application yet.
Authors
Chenyu Wang
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.