Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909649166401536 |
|---|---|
| author | Yang, Guangxu Zhang, Jiapeng |
| author_facet | Yang, Guangxu Zhang, Jiapeng |
| contents | 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 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 $Ω(\frac{n^{1/(k-1)}}{k^k})$ vs. $O(\log n)$ for $k$ players, as shown by Viola and Wigderson (FOCS 2007).
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)$, further demonstrating the broader applicability of our methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12420 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication Yang, Guangxu Zhang, Jiapeng Computational Complexity 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 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 $Ω(\frac{n^{1/(k-1)}}{k^k})$ vs. $O(\log n)$ for $k$ players, as shown by Viola and Wigderson (FOCS 2007). 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)$, further demonstrating the broader applicability of our methods. |
| title | Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.12420 |