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

Abstract

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 exact optimisation and of hardness of approximation. Assuming the Exponential Time Hypothesis, there is a computable, nondecreasing additive error allowance tending to infinity for which approximation is impossible in polynomial time. The proof uses interlacing, which asks the players to solve one problem selected by Alice from a collection of inputs held by Bob. For suitable matrices, a short protocol must reveal enough of Alice's selection to encode a solution to a combinatorial problem. This produces a one-bit communication gap in a polynomial-size matrix and proves exact hardness. Repeating the construction is harder: earlier messages can remove the inputs on which a later lower bound depends. Restriction bounds that survive the construction make the one-bit gain repeatable. A smaller, balanced family of interlaced columns controls the truth-table size. For every fixed number of applications, the construction takes subexponential time in the source length. This rules out every fixed additive error under ETH. A general computability argument then yields the stated unbounded allowance.

arXiv comment74 pages, 5 figures. Substantially revised and expanded from v4. Retains NP-completeness and adds ETH-based additive inapproximability: hardness for every fixed additive error and for one computable, nondecreasing unbounded allowance. Simplified exact-hardness proof; repeatable gap amplification with explicit truth-table size and running-time bounds