NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing

Serge Gaspers, Tao Zixu He, Simon Mackenzie

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,…