# NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing

arXiv: https://arxiv.org/abs/2508.05597 · HTML: https://mlsanity.com/paper/2508.05597/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2025.

## Built on by (most cited first, 1 of 1)

- [Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening](https://mlsanity.com/paper/2608.05327/) (2026)

## Abstract (arXiv)

We prove that computing the deterministic communication complexity of a Boolean function, given its truth table, is textsfNP-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 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 textsfNP-completeness theorem as their main application here.