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.