{"ID":2885361,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.05597","arxiv_id":"2508.05597","title":"NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing","abstract":"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, 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 \\emph{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 \\textsf{NP}-completeness theorem as their main application here.","short_abstract":"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, addressing a meta-complexity question raised by Yao in 1979. The reduction is from \\(\\{0,1\\}\\)-Vector Bin Packing and produces, in polynomia...","url_abs":"https://arxiv.org/abs/2508.05597","url_pdf":"https://arxiv.org/pdf/2508.05597v4","authors":"[\"Serge Gaspers\",\"Tao Zixu He\",\"Simon Mackenzie\"]","published":"2025-08-07T17:39:40Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}