Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
Guangxu Yang, Jiapeng Zhang · 2025
Read Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication by Guangxu Yang, Jiapeng Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12420.txt.
Introduction
Guangxu Yang and Jiapeng Zhang wrote this paper in two thousand twenty-five. It proves a lifting theorem that moves one-way communication bounds from two players to the many-player number-on-forehead game.
In that game each player sees all inputs but their own. Lifting theorems are a main tool for lower bounds in talks, with uses in proofs, circuits, and data structures, but past ones stuck to two players. The new deterministic lift turns one-way two-party bounds into one-way forehead bounds. It yields a sharp split between random and fixed play, even with many players, and a sharp split between one and two rounds. A fresh proof for the disjointness bound shows the reach.
Catalog record
| CREATOR | Guangxu Yang, Jiapeng Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-12420
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication Guangxu Yang, Jiapeng Zhang Abstract Lifting theorems are one of the most powerful tools for proving communication lower bounds, with numerous downstream applications in proof complexity, monotone circuit lower bounds, data structures, and combinatorial optimization. However, to the best of our knowledge, prior lifting theorems have primarily focused on the two-party communication. In this paper, we propose a new lifting theorem that establishes connections between the two-party communication and the Number-on-Forehead (NOF) communication model. Specifically, we present a deterministic lifting theorem that translates one-way two-party communication lower bounds into one-way NOF lower bounds. Our lifting theorem yields two applications. First, we obtain an optimal explicit separation between randomized and deterministic one-way NOF communication , even in the multi-player setting. This improves the prior square-root vs. constant separation for three players established by Kelley and Lyu (arXiv 2025). Second, we achieve optimal separations between one-round and two-round deterministic NOF communication, improving upon the previous separation of Ω ( n 1 / ( k − 1 ) k k ) \Omega\left(\frac{n^{1/(k-1)}}{k^{k}}\right) vs. O ( log n ) O(\log n) for k k players, as shown by Viola and Wigderson (FOCS 2007). On the technical side, we use the generalized inner product function over large fields (GIP) as the gadget. As a bonus result, we construct an explicit function that for any number of players k k , at least Ω ( n / 2 k ) \Omega(n/2^{k}) bits of communication are required to solve it, even for randomized NOF protocols. This improves the previous best bound of Ω ( n / 4 k ) \Omega(n/4^{k}) for generalized inner product over the binary field, established by Babai, Nisan, and Szegedy (STOC 1989). Beyond the lifting theorems, we also apply our techniques to the disjointness problem. In particular, we provide a new proof that the deterministic one-way three-party NOF communication complexity of set disjointness is Ω ( n ) \Omega(n) , further demonstrating the broader applicability of our methods. 1 Introduction Lifting theorems are a generic method for translating lower bounds from weaker computational models to relatively stronger ones. A representative example of lifting theorems is the query-to-communication lifting theorems, which convert lower bounds in query complexity into communication complexity lower bounds, using a suitable base function composed with a gadget. There has been a long line of work developing query-to-communication lifting theorems, with diverse applications in various areas such as monotone circuit complexity, proof complexity, combinatorial optimization, and more [ RM97 , Zha09 , GPW18 , PR17 , GPW20 , CFK+19 , LMM+22 , YZ24 , MYZ25 ] . Though these lifting theorems have achieved significant success, to the best of our knowledge, all existing lifting theorems have focused on two-party communication models (or on a slight generalization known as the Number-in-Hand model). No lifting theorems have yet been established for the more powerful models, such as the Number-on-Forehead (NOF) models. Compared to two-party communication lower bounds, lower bounds in NOF models are known to have more connections to several major open problems. However, existing lower bound techniques for NOF models remain quite limited. Motivated by this, papers by Kumar, Meka, and Zuckerman [ KMZ20 ] and Toniann Pitassi [ Pit21 ] raised a natural question: Can we develop lifting theorems in NOF models and derive interesting applications? Though this problem is well-motivated, it remains wide open. Furthermore, we do not even have good candidates for conjectured statements for the lifting theorem in NOF models. In this paper, we propose a lifting theorem that converts two-party communication lower bounds into lower bounds in the NOF models. As a first step in this direction, we prove a deterministic lifting theorem that lifts one-way communication lower bounds in the two-party setting to one-way communication lower bounds in NOF protocols. Although the one-way NOF model may seem like a restricted variant of the general NOF model, since each player is allowed to speak only once in a fixed order, it still enables many surprising applications. Notably, it has been instrumental in proving strong lower bounds in areas such as circuit complexity [ HG90 , PRS97 , Cha07 , VW07 ] , cryptography [ CKGS98 , BDFP17 ] , and streaming algorithms [ KMPV19 , VW07 ] . Despite its restricted nature, proving lower bounds in the one-way NOF model remains a highly challenging and fundamental problem. 1.1 Our Contribution In this paper, we propose a new form of lifting two-party communication problems into NOF communication problems. Definition 1.1 . For any two-party function f:[q]\times[q]\rightarrow\{0,1\} and a gadget function g^{k}:[N]^{k}\rightarrow[q] , the lifted problem over (k+1) players, denoted by, f\circ g^{k}:[N]\times\cdots\times[N]\times[q]\rightarrow\{0,1\} , is defined as f\circ g^{k}(x_{1},\dots,x_{k},z)=f(z,g^{k}(x_{1},\dots,x_{k})). In the NOF setting, we assume that the (k+1) -th player knows the input (x_{1},\dots,x_{k}) , while each of the remaining i -th players knows all inputs except x_{i} . We observe that many well-known problems in the NOF model can be expressed as lifted problems of the form f\circ g . Examples include Generalized Inner Product [ RY20 ] , Set Disjointness [ RY20 ] , Pointer Jumping [ VW07 , Cha07 ] , Shifting [ PRS97 ] , and the Exactly- N problem [ CFL83 ] . As a quick example, consider the Exactly- N problem: Alice, Bob, and Charlie are given integers x , y , and z , and the goal is to determine whether x+y+z=N . We can express this as a composition \mathrm{EQ}\circ g by defining g(x,y):=N-x-y , and \mathrm{EQ}(z,s)=1 if and only if z=s . Then, the condition x+y+z=N holds if and only if f(z,g(x,y))=1 . In this paper, we primarily use the generalized inner production function as the gadget g . Definition 1.2 . Let q be a prime and k,r>0 . We define the function \mathrm{GIP}_{q,r}^{k}:(\mathbb{F}_{q}^{r})^{k}\rightarrow\mathbb{F}_{q} by \mathrm{GIP}_{q,r}^{k}(x_{1},\dots,x_{k})=\sum_{j\in[r]}\prod_{i\in[k]}x_{i,j}, where \mathbb{F}_{q} is a prime field, and all arithmetic operations are over \mathbb{F}_{q} . When q,r,k are clear from context, we write \mathrm{GIP}(x_{1},\dots,x_{k}) for simplicity. Using the generalized inner product function, we show that for any two-party function f , the one-way communication lower bound of f , denoted \mathrm{OCC}(f) , can be lifted to a one-way NOF lower bound of f\circ\mathrm{GIP} , denoted \mathrm{OCC^{NOF}}(f\circ\mathrm{GIP}) . Theorem 1.3 . Let q be a prime and k,r\geq 2^{k+1} . For any Boolean function f:[q]\times[q]\rightarrow\{0,1\} , we have \mathrm{OCC^{NOF}}(f\circ\mathrm{GIP}_{q,r}^{k})=\Theta(\mathrm{OCC}(f)). Although we only prove the theorem for one-way communication, we conjecture that it also holds for general NOF communication. 1.1.1 Applications of Our Main Theorem We now discuss some applications of our main theorem. Deterministic vs. randomized separation. One of the central goals in communication complexity is understanding the power of randomized communication. Separations between deterministic and randomized communication complexity in NOF have received a good amount of attention in recent years [ BDPW10 , KLM24 , JLL+25 , KL25 ] . Beame, David, Pitassi, and Woelfel [ BDPW10 ] showed the existence of a three-party function f:[N]^{3}\to\{0,1\} with randomized NOF complexity O(1) and deterministic NOF complexity \Omega(\log N) . However, their result was non-explicit, relying on a counting argument. For explicit constructions, the Exactly-N function introduced by [ CFL83 ] has long been considered a strong candidate for such separations. While its