NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917402271285248 |
|---|---|
| author | Gaspers, Serge He, Tao Zixu Mackenzie, Simon |
| author_facet | Gaspers, Serge He, Tao Zixu Mackenzie, Simon |
| contents | We prove that computing the deterministic communication complexity of a Boolean function, given its truth table, is \textsf{NP}-complete in the standard protocol-tree-depth model, addressing a meta-complexity question raised by Yao in 1979. The reduction is from \(\{0,1\}\)-Vector Bin Packing and produces, in polynomial time, a communication matrix whose optimal protocol depth exhibits a one-bit gap between satisfiable and unsatisfiable instances. The main technical contribution is the \emph{relaxed-interlacing} framework that makes this reduction possible. It replaces exponential-size Cartesian products with polynomial-size almost \(t\)-wise independent column sets, a pseudorandom substitute for full products, while preserving the lower-bound and protocol-control statements needed for the reduction. We develop these statements in two stages: first for classical interlacing, where projection arguments give clean lower bounds and separation statements, and then for relaxed interlacing, where a bridge lemma recovers the classical lower-bound and separation statements with controlled density loss. This leads to an extension theorem that lifts the classical lower bound to the relaxed setting and a near-exact separation theorem that lifts the corresponding protocol-control statement, with the present \textsf{NP}-completeness theorem as their main application here. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_05597 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing Gaspers, Serge He, Tao Zixu Mackenzie, Simon Computational Complexity Data Structures and Algorithms Combinatorics We prove that computing the deterministic communication complexity of a Boolean function, given its truth table, is \textsf{NP}-complete in the standard protocol-tree-depth model, addressing a meta-complexity question raised by Yao in 1979. The reduction is from \(\{0,1\}\)-Vector Bin Packing and produces, in polynomial time, a communication matrix whose optimal protocol depth exhibits a one-bit gap between satisfiable and unsatisfiable instances. The main technical contribution is the \emph{relaxed-interlacing} framework that makes this reduction possible. It replaces exponential-size Cartesian products with polynomial-size almost \(t\)-wise independent column sets, a pseudorandom substitute for full products, while preserving the lower-bound and protocol-control statements needed for the reduction. We develop these statements in two stages: first for classical interlacing, where projection arguments give clean lower bounds and separation statements, and then for relaxed interlacing, where a bridge lemma recovers the classical lower-bound and separation statements with controlled density loss. This leads to an extension theorem that lifts the classical lower bound to the relaxed setting and a near-exact separation theorem that lifts the corresponding protocol-control statement, with the present \textsf{NP}-completeness theorem as their main application here. |
| title | NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing |
| topic | Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2508.05597 |