Numbers-on-Forehead (NOF) communication model is a central model in communication complexity. As a restricted variant, one-way NOF model is of particular interest. Establishing strong one-way NOF lower bounds has applications in circuit complexity, additive combinatorics, and cryptography. However, proving such lower bounds directly remains highly challenging due to a lack of effective techniques, leaving many fundamental questions wide open.
In this paper, we propose a new lifting theorem that establishes connections between \textit{two-party} communication and \textit{Numbers-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.
By our lifting theorem, we construct an explicit $k$-player function $f:[N]^k \rightarrow \{0,1\}$ such that: there exists a $k$-party randomized one-way NOF protocol computing it that sends a constant number of bits; but any $k$-party deterministic one-way NOF protocol computing it requires sending about $\Omega(\frac{\log N}{2^k})$ bits. In fact, our separation applies to a generalization of $k$-player one-way communication, where the first $k-1$ players speak freely, and the last player speaks once. At present, the best separation between deterministic and randomized NOF is $\Omega(\sqrt{\log N})$ vs $O(1)$ for three-party, due to Kelley and Lyu (FOCS 2025). Prior to our work, no stronger lower bound was known for any restricted communication model and for any number of players.
Beyond the lifting theorems, we demonstrate the versatility of our techniques by revisiting the Set Disjointness problem. We provide a simplified, alternative proof that the deterministic one-way three-party NOF complexity of disjointness is $\Omega(n)$, offering a new perspective on this classic problem beyond traditional discrepancy methods.
Added an introduction to the importance of one-way NOF communication and fixed some typos.
Lifting theorems are one of the most powerful tools for proving communication complexity 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 \textit{optimal separations} between one-round and two-round deterministic NOF communication, improving upon the previous separation of \( \Omega\left(\frac{n^{1/(k-1)}}{k^k}\right) \) vs.\( O(\log n) \) for \( 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$, at least $\Omega(n / 2^k)$ bits of communication are required to solve it, even for randomized NOF protocols. This improves the previous best bound of $\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 $\Omega(n)$, further demonstrating the broader applicability of our methods.
