NP-Completeness and ETH-Based Additive Inapproximability of Deterministic Communication Complexity via Relaxed Interlacing

Serge Gaspers, Tao Zixu He, Simon Mackenzie

How difficult is it to find an efficient communication protocol when the entire truth table of the function is given? We give a unified interlacing proof of NP-completeness for exa…