← All papers
First page of NP-Hardness and Additive Inapproximability of Deterministic Communication Complexity

NP-Hardness and Additive Inapproximability of Deterministic Communication Complexity

Serge Gaspers, Tao Zixu He, Simon Mackenzie

cs.CC Aug 7, 2025 · v6 cs.DS math.CO
A companion Lean development machine-checks the reduction constructions and their consequences for communication complexity and 3-SAT running times, with a public proof inspector.
Given the full truth table of a Boolean function whose input is split between two players, we study the complexity of determining the minimum worst-case number of bits they must communicate to compute it. This is a basic meta-complexity question, posed by Yao in 1979. We prove NP-hardness of approximation within every fixed additive error for deterministic communication complexity, under deterministic polynomial-time reductions. The result holds both in the standard model and in Yao's original model, where the players alternate after every bit and only the receiver of the last bit must determine the answer. In particular, it resolves the exact computation question under Yao's original conventions. Earlier versions of this same paper established exact NP-hardness for the standard model, independently and concurrently with Hirahara, Ilango, and Loff. In both models, a polynomial-time estimator with any fixed additive error would yield a polynomial-time $3$-SAT algorithm, deterministic or bounded-error randomized according to the estimator. For the standard model, we also give quantitative implications for errors that grow with the number $T$ of table entries. A bounded-error randomized polynomial-time estimator with additive error $c\log T/\log\log T$, for any fixed $0\le c<1/8$, yields a bounded-error randomized $3$-SAT algorithm on $N$ variables and $O(N)$ clauses running in time $2^{O(N^α)}$ for every fixed $8c<α<1$. A deterministic polynomial-time estimator with additive error $c_*\log\log T$, for an effective absolute constant $c_*>0$, yields a deterministic algorithm running in time $2^{O((\log N)^2)}$ on such formulas.

Yao asked in 1979 how hard it is to compute the deterministic communication complexity D(M) of a fully specified Boolean table. Earlier work showed exact NP-hardness in the standard model. Hardness with additive error and hardness in Yao's original strict-alternation model remained open.

A 3-SAT formula is reduced to a bounded-degree graph that is robustly non-3-colorable in the NO case. The graph is encoded into interlaced copies of a base matrix so that a monochromatic edge forces one extra bit. Deletion-robust lower bounds make this one-round amplifier repeatable. Full products are replaced by small exactly 8192-wise independent tuple lists to keep each round polynomial-time. The constructions and their consequences are machine-checked in a companion Lean development, written with AI assistance.

Approximating D(M) within any fixed additive error is NP-hard under deterministic polynomial-time reductions, both in the standard model and in Yao's alternating model. Estimators with error c log T/log log T (c<1/8) or c* log log T would yield subexponential or quasi-polynomial 3-SAT algorithms, respectively.

Protocol modelAdditive errorImplied 3-SAT algorithmAlgorithm type
UnrestrictedEvery fixed errorPolynomial timeSame as estimator
Strict alternationEvery fixed errorPolynomial timeSame as estimator
Unrestrictedc* log log T2^{O((log N)^2)}Same as estimator
Unrestrictedc log T / log log T, c<1/82^{O(N^α)}, every 8c<α<1Randomized
Implications of an additive-error estimator for 3-SAT