REVIEW 3 major objections 5 minor 1 cited by
Communication Complexity is NP-hard
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read The paper proves that deciding whether a function's two-party communication complexity is at most a given k is NP-complete, by reducing from vertex cover.
desk verdict First NP-hardness for exact protocol-tree communication complexity, but the submitted write-up has a sign error in the padding argument; likely fixable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the 1-partition number $\chi_1(f)$: the minimum number of pairwise disjoint all-ones subrectangles needed to cover the ones of a communication matrix. A protocol's leaves form such a partition, giving $CC(f) \ge \lceil \log \chi_1(f) \rceil$. The paper proves the slightly stronger bound $CC(f) \ge \lceil \log \chi_1(f) \rceil + 1$ for non-constant f by induction on protocol depth. The other key mechanism is a padding recipe: adding a block-diagonal identity matrix and choosing d so that the two branches of a near-balanced protocol for f_G each have exactly $2^\ell$ leaves, making the binary depth exactly $\ell+2$. Together with the exact formula $\chi_1(f_G)=n+4|E|+\kappa(G)$ from the vertex-cover reduction, these pieces produce a one-unit gap between the two cases.
What would settle it
Brute-force compute the minimum number of disjoint all-ones subrectangles in $f_G$ for every graph on at most six vertices and compare each value with $n + 4|E| + \kappa(G)$; any mismatch would show the exact formula that anchors the reduction is false.
Extended reading notes
Core claim
Given a graph G and an integer k, the paper constructs a communication matrix f'_G by taking the matrix f_G from a known vertex-cover reduction (which satisfies $\chi_1(f_G) = n + 4|E| + \kappa(G)$) and padding it with a block-diagonal identity matrix of size d, where d is chosen so that both branches of a near-balanced protocol for f_G would have exactly $2^\ell$ leaves. The paper proves that $CC(f'_G) = \ell+2$ when $\kappa(G) \le k$ and $CC(f'_G) \ge \ell+3$ when $\kappa(G) > k$; therefore deciding whether $CC(f) \le k$ is NP-complete. The exact gap is certified by the paper's lemma that every non-constant f satisfies $CC(f) \ge \lceil \log \chi_1(f) \rceil + 1$, a strengthening of the trivial leaf-count bound.
Load-bearing premise
The whole construction rests on the exact equality between a graph's vertex-cover size and the minimum number of disjoint all-ones subrectangles in the associated matrix; if that equality fails for any graph, the one-round separation between the two cases no longer follows.
Editorial extensions
If this is right
- If $CC(f) \le k$ could be decided in polynomial time, then the vertex cover problem would be in P, so no such algorithm exists unless P = NP.
- The cryptographic hardness previously shown for this decision problem is superseded by NP-hardness under standard complexity assumptions.
- The proof gives no hardness for approximating $CC(f)$ to within an additive error of 1, leaving open the possibility that near-optimal protocols can be found efficiently.
- The original alternating-round model of communication complexity remains unresolved, because the reduction is not robust to the factor-of-two difference between the two definitions.
- Any constant-factor hardness of approximation for $CC(f)$ must come from a different starting point, such as graph coloring, since vertex cover is 2-approximable.
Reading between the lines
- The padding trick, adding an identity block sized to balance a near-balanced protocol, may transfer to other decision problems about protocol structure wherever a natural unbalanced tree can be padded into an exact-depth balanced one.
- The +1 strengthening of the leaf-count lower bound suggests exact depth is controlled by the 1-partition number more tightly than the trivial logarithm; testing whether a similar bound holds for leaf complexity under balancedness conditions could be a useful check.
- If the underlying vertex-cover reduction could be made approximation-preserving from a harder-to-approximate problem, the same padding construction might yield NP-hardness of approximation for CC; the paper notes the exact technique is too brittle for that.
- The knife-edged one-unit gap means the hardness is fragile: even a small additive slack in the decision problem would make the reduction vacuous, hinting that exact communication complexity might be easy to approximate in practice.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims NP-hardness of deciding, given a communication matrix and an integer k, whether the deterministic communication complexity CC(f) is at most k, under the standard protocol-tree model. The proof adapts a reduction of Jiang and Ravikumar showing that the 1-partition number of a graph-derived matrix f_G equals n + 4|E| + κ(G), then pads f_G with an identity block to balance a non-binary protocol, proves a lower bound CC(f) ≥ ceil(log χ1(f)) + 1, and concludes that the padded matrix has CC either ℓ+2 or ℓ+3 depending on vertex cover size. As written, however, the final reduction contains a direction error in the inequalities, and the padded protocol is not fully specified.
Significance. If the proof is corrected, the paper would provide the first NP-hardness result for exact deterministic communication complexity in the standard protocol-tree model, making progress on a long-standing question of Yao. The paper is concise, identifies its reliance on the Jiang-Ravikumar lemma, and is honest about the fact that Yao's original alternating-round model remains open. The padding idea and the lower-bound lemma in Section 6 are elegant, and the exposition is generally clear. The current manuscript, however, has a load-bearing sign error in the reduction and an incomplete protocol description, so the central claim is not yet established as written.
major comments (3)
- [§5] The reduction direction is reversed. The text states that the goal is to distinguish κ(G) ≤ k from κ(G) > k, but the subsequent claims put the low-CC case at κ(G) ≥ k: Section 5 says the protocol has depth exactly ℓ+2 if k ≤ κ(G), and Section 7 says CC(f′G) ≥ ℓ+3 if k > κ(G). These conditions are incompatible with the stated goal. Using the definitions of Section 5, χ1(f′G) = 2^{ℓ+1} + κ(G) − k; if k > κ(G), then χ1(f′G) < 2^{ℓ+1} and the bound of Section 6 gives CC(f′G) ≥ ℓ+2, not ℓ+3. The arithmetic works only after swapping the inequalities: the construction yields CC(f′G) = ℓ+2 when κ(G) ≤ k and CC(f′G) ≥ ℓ+3 when κ(G) > k. As written, the reduction would be from the coNP-complete problem κ(G) ≥ k, which does not establish NP-hardness. This must be corrected, and the threshold target (f′G, ℓ+2) should be stated explicitly.
- [§5] The protocol for the padded matrix f′G is underspecified. Bob's first bit is said to cover the NFCV columns or the last d1 extra columns, and Alice's extra case (5) is defined only for the first d0 extra rows. If Bob's first bit is 0 and Alice's row is one of the last d1 extra rows, no message or output rule is specified, yet such inputs occur and the value is 0 in that branch (since the corresponding 1-entry would require a last d1 extra column, which is in the other branch). Please complete the protocol for all extra rows, for example by adding an explicit default 'extra row' case, and verify that the message-space size and depth remain within ℓ+2 in the κ(G) ≤ k case.
- [§3] The proof of the lower bound χ1(fG) = n + 4|E| + κ(G) is too compressed for a load-bearing step. The 'without loss of generality' normalization involving the rows (i,0) and (i,1) and the claim that edges in E1 require at least 5 rectangles via a fooling set are only sketched, and the latter refers to a figure that is not reproduced in the text. Since this equality is the quantitative foundation for the gap in Section 7, either provide a complete, self-contained proof of the lemma or state clearly that this is a direct consequence of Lemma 3.3 of Jiang and Ravikumar and defer all details to that citation, with a precise statement of how the normal-set-basis formulation translates to communication matrices.
minor comments (5)
- [§6] The induction proof of CC(f) ≥ ceil(log χ1(f)) + 1 does not define ceil(log χ1(g)) when one of the subfunctions g is the all-zero function, for which χ1(g) = 0. This case can be repaired by observing that an all-zero subfunction contributes no 1-rectangles and can be dropped from the max, but the manuscript should say so explicitly.
- [§5] The quantities d0 and d1 are added to message spaces, not directly to leaf counts; the text calls them 'the number of leaves that are missing,' which is confusing because each added message leads to two leaves after the final reply bit. Please reword the definitions to refer to missing messages or to state the leaf count convention explicitly.
- [§4–§5] The protocol of Section 4 uses a vertex cover C, but the text does not state that C is a minimum vertex cover of size κ(G). This should be made explicit, since the later leaf counts and the balanced-depth claim use 2κ(G) rather than an arbitrary |C|.
- [§7] The final conclusion should state the many-one reduction explicitly: the vertex-cover instance (G,k) is mapped to the communication instance (f′G, ℓ+2), where ℓ is defined as in Section 5, so that κ(G) ≤ k iff CC(f′G) ≤ ℓ+2.
- [§6] There is a small typographical error in the displayed induction: 'χ1(f0) + χ1(f1)})' contains an extra brace that should be removed.
Circularity Check
No circularity: the hardness reduction rests on an external lemma and explicit protocols, not on its own conclusion.
full rationale
The paper's derivation chain is: (i) import the external Jiang–Ravikumar result that for the constructed matrix f_G, χ1(f_G) = n + 4|E| + κ(G); (ii) pad f_G with an identity block to obtain f'_G whose 1-partition number is 2^{ℓ+1} + κ(G) − k; (iii) exhibit an explicit protocol that achieves depth ℓ+2 in the intended low-CC case; and (iv) use the independent combinatorial lower bound CC(f) ≥ ⌈log χ1(f)⌉ + 1 to obtain the matching lower bound. None of these steps defines CC(f) in terms of the target decision problem, fits a parameter to the yes/no instances and then reports it as a prediction, or invokes a result proved only by the present authors. The only load-bearing external input is the Jiang–Ravikumar formula, which is prior work by different authors and not a self-citation; the paper even sketches both directions of that formula in §3. Any concerns about the direction of the k inequality or the ℓ+2/ℓ+3 arithmetic are correctness issues, not circularity.
Assumptions & free parameters
assumptions (3)
- standard math NP-hardness of Vertex Cover
- domain assumption Jiang-Ravikumar formula χ1(f_G) = n + 4|E| + κ(G)
- domain assumption Communication complexity is defined by protocol-tree depth, not alternating rounds
Cite this review
Pith. "Pith review of Communication Complexity is NP-hard." pith.science (2026). https://pith.science/paper/2OGC3TAW
@misc{pith2026250710426,
author = {Pith},
title = {Pith review of: Communication Complexity is NP-hard},
year = {2026},
howpublished = {\url{https://pith.science/paper/2OGC3TAW}},
note = {Machine review of arXiv:2507.10426}
}
abstract
In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. Kushilevitz and Weinreb have shown that this problem is cryptographically hard. Here we show it is NP-hard.
Forward citations
Cited by 1 Pith paper
-
Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening
If an optimal (even intractable) protocol achieves utility α in k bits, a polynomial-time algorithm can find a protocol achieving α−ε using 2^{O(k)}/ε^2 bits, and this is tight up to a constant in the exponent.
Reference graph
Works this paper leans on
-
[1]
Tao Jiang and Bala Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing , 22(6):1117--1141, 1993
work page 1993
-
[2]
On the complexity of communication complexity
Eyal Kushilevitz and Enav Weinreb. On the complexity of communication complexity. In Symposium on Theory of Computing (STOC) , pages 465--474, 2009
work page 2009
-
[3]
Some complexity questions related to distributive computing
Andrew Chi-Chih Yao. Some complexity questions related to distributive computing. In Symposium on Theory of Computing (STOC) , page 209–213, 1979
work page 1979
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.