pith. sign in

arxiv: 2508.05597 · v4 · submitted 2025-08-07 · 💻 cs.CC · cs.DS· math.CO

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing

Serge Gaspers , Tao Zixu He , Simon Mackenzie This is my paper

Pith reviewed 2026-05-19 00:17 UTC · model grok-4.3

classification 💻 cs.CC cs.DSmath.CO
keywords NP-completenessdeterministic communication complexityBoolean functionsprotocol tree depthvector bin packingrelaxed interlacingmeta-complexitycommunication matrix
0
0 comments X

The pith

Computing the deterministic communication complexity of a Boolean function from its truth table is NP-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that finding the minimum depth of a deterministic protocol tree for a Boolean function, when the function is given explicitly as a truth table, cannot be done efficiently unless P equals NP. This resolves a long-standing meta-complexity question by showing hardness for an exact computation task rather than an approximation. The argument proceeds by a polynomial-time reduction from vector bin packing that embeds the feasibility question into the communication matrix so that satisfiable instances admit a protocol one bit shorter than unsatisfiable ones. The technical engine is a relaxed-interlacing construction that replaces enormous Cartesian products with small, almost t-wise independent column sets while still supporting the projection lower bounds and protocol-separation statements required for the gap.

Core claim

We prove that computing the deterministic communication complexity of a Boolean function, given its truth table, is NP-complete in the standard protocol-tree-depth model. 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 relaxed-interlacing framework that replaces exponential-size Cartesian products with polynomial-size almost t-wise independent column sets while preserving the lower-bound and protocol-control statements needed for the reduction.

What carries the argument

The relaxed-interlacing framework, which substitutes polynomial-size almost t-wise independent column sets for full Cartesian products while retaining projection arguments for lower bounds and separation statements for protocol control.

If this is right

  • No polynomial-time algorithm exists for computing exact deterministic communication complexity on arbitrary Boolean functions unless P equals NP.
  • The one-bit gap in protocol depth distinguishes satisfiable from unsatisfiable instances in the constructed matrices.
  • The same reduction technique yields NP-hardness for deciding whether communication complexity is at most k for any fixed k greater than or equal to some constant.
  • Protocol-control statements lift from the classical interlacing setting to the relaxed setting with only small density overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar pseudorandom replacements for Cartesian products could be used to prove hardness for computing other exact communication measures such as nondeterministic or quantum complexity.
  • The framework supplies a general template for embedding combinatorial search problems into communication matrices while keeping matrix size polynomial.
  • If the density loss in the relaxed construction can be made logarithmic, the same approach might separate communication complexity from circuit size in explicit constructions.

Load-bearing premise

The almost t-wise independent column sets must preserve the classical projection lower bounds and protocol-control properties with only controlled density loss.

What would settle it

A polynomial-time algorithm that, on every communication matrix produced by the reduction, outputs a protocol whose depth exactly matches the satisfiability status of the underlying vector bin packing instance.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proves that computing the deterministic communication complexity of a Boolean function, given its truth table, is NP-complete in the protocol-tree-depth model. The proof is a polynomial-time reduction from the NP-complete {0,1}-Vector Bin Packing problem that produces a communication matrix whose optimal deterministic protocol depth has a strict one-bit gap between satisfiable and unsatisfiable instances. The key technical device is the relaxed-interlacing framework, which replaces exponential Cartesian products with polynomial-size almost t-wise independent column sets while preserving the required lower-bound and protocol-control properties; this is developed first for classical interlacing via projection arguments and then lifted to the relaxed case via a bridge lemma that recovers the classical statements with controlled density loss, together with an extension theorem and a near-exact separation theorem.

Significance. If the central reduction holds, the result resolves the meta-complexity question posed by Yao in 1979. The relaxed-interlacing framework supplies a general pseudorandom substitute for product constructions that may be reusable in other communication-complexity lower-bound arguments. The paper defines the new framework independently of the target result and reduces from an established NP-complete problem rather than a self-referential construction.

major comments (2)
  1. [Bridge lemma] Bridge lemma (relaxed-interlacing development): the lemma is stated to recover the classical projection-based lower bound and the separation statement with only controlled density loss after substituting almost t-wise independent column sets. No explicit calculation of the cumulative density loss for the concrete parameters t and density chosen in the reduction is supplied, so it remains unclear whether the final lower bound on unsatisfiable instances stays strictly above the upper bound on satisfiable instances, which is required for the one-bit gap.
  2. [Extension and separation theorems] Extension theorem and near-exact separation theorem: these lift the classical statements to the relaxed setting. The manuscript must verify that the almost t-wise independence preserves the necessary projection and protocol-control properties after the density adjustment; without such verification the one-bit gap claimed for the Vector Bin Packing reduction is not yet established.
minor comments (2)
  1. [Abstract] The abstract refers to a 'near-exact separation theorem' without giving its precise quantitative statement; an early formal definition would improve readability.
  2. [Notation and definitions] Notation for almost t-wise independent column sets would benefit from a short concrete example illustrating the independence parameter t and the resulting density.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. The two major comments correctly identify places where the manuscript would benefit from more explicit calculations and verifications to confirm preservation of the one-bit gap. We will incorporate these additions in the revised version.

read point-by-point responses

  1. Referee: [Bridge lemma] Bridge lemma (relaxed-interlacing development): the lemma is stated to recover the classical projection-based lower bound and the separation statement with only controlled density loss after substituting almost t-wise independent column sets. No explicit calculation of the cumulative density loss for the concrete parameters t and density chosen in the reduction is supplied, so it remains unclear whether the final lower bound on unsatisfiable instances stays strictly above the upper bound on satisfiable instances, which is required for the one-bit gap.

    Authors: We agree that an explicit calculation for the concrete parameters is needed. While the bridge lemma bounds density loss in general, the reduction uses specific values of t and density for the almost t-wise independent sets. In the revision we will add a short calculation (in a new paragraph or appendix) that plugs these parameters into the loss bound and verifies that the resulting lower bound on unsatisfiable instances remains at least one bit above the upper bound on satisfiable instances. revision: yes

  2. Referee: [Extension and separation theorems] Extension theorem and near-exact separation theorem: these lift the classical statements to the relaxed setting. The manuscript must verify that the almost t-wise independence preserves the necessary projection and protocol-control properties after the density adjustment; without such verification the one-bit gap claimed for the Vector Bin Packing reduction is not yet established.

    Authors: We acknowledge the need for an explicit verification step. The extension and near-exact separation theorems are written to lift the classical projection and protocol-control properties while accounting for density loss, but the manuscript does not spell out the error terms introduced by almost t-wise independence after adjustment. In the revision we will insert a short verification paragraph (or lemma) that bounds these error terms using standard concentration properties of almost t-wise independent families and shows they are small enough to preserve the strict one-bit gap in the Vector Bin Packing reduction. revision: yes

Circularity Check

0 steps flagged

Reduction from established NP-complete problem using independently developed framework

full rationale

The paper establishes NP-completeness of deterministic communication complexity via a direct polynomial-time reduction from the known NP-complete problem {0,1}-Vector Bin Packing. The relaxed-interlacing framework, bridge lemma, extension theorem, and near-exact separation theorem are all introduced and proven within the paper itself, first for classical interlacing and then lifted to the relaxed setting with explicit density-loss controls. No step in the derivation chain reduces to a fitted parameter, self-definition, or load-bearing self-citation; the one-bit gap is obtained by applying the newly proven statements to the constructed communication matrix. The central claim therefore remains independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The proof rests on standard combinatorial properties of almost t-wise independent sets and projection arguments; no free parameters are fitted to data and no new physical or computational entities are postulated beyond the definitional framework of relaxed interlacing.

axioms (2)
  • domain assumption Properties of almost t-wise independent column sets suffice to preserve projection lower bounds and protocol separation statements up to controlled density loss.
    Invoked in the bridge lemma and extension theorem that lift classical interlacing results to the relaxed setting.
  • standard math Standard mathematical facts about protocol trees and deterministic communication complexity (depth equals communication cost).
    Background assumption used throughout the reduction construction.
invented entities (1)
  • relaxed-interlacing framework no independent evidence
    purpose: Substitute for exponential Cartesian products in the reduction while preserving lower-bound and protocol-control statements
    New technical device introduced in the paper; independent evidence consists of the claimed bridge lemma and near-exact separation theorem.

pith-pipeline@v0.9.0 · 5763 in / 1488 out tokens · 41530 ms · 2026-05-19T00:17:22.091727+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.