REVIEW 2 major objections 3 minor 23 references
Equality is Far Weaker than Constant-Cost Communication
T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read There is a constant-cost randomized communication problem that any deterministic Equality-oracle protocol needs $\Theta(\sqrt{n})$ queries to solve.
desk verdict The main separation is real and the analytic proof holds up; the flagged issues are minor typos that should be corrected but do not threaten the result. 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 key object is the XOR function $f(M)=1$ iff $M\in\mathbb{F}_2^{n\times n}$ has rank at most one, with $\mathrm{RankOne}_n(A,B)=f(A\oplus B)$. The upper bound rests on a randomized parity decision tree of constant depth: query the parity of $M$ on a random $2\times2$ submatrix, which preserves rank-one inputs and, with constant probability, exposes rank-two inputs. The analytic lower bound uses the $\gamma_2$-norm of the communication matrix, the inequality $\frac12\log\gamma_2(M)\le D^{\mathrm{Eq}}(M)$, and a Hölder-inequality estimate bounding $\gamma_2$ from the Frobenius norm and $\mathrm{tr}((M^\top M)^2)$; the proof counts triples of rank-one matrices whose sum is rank-one. The combinatorial lower bound uses the blocky cover number $\mathrm{bc}(\cdot)$, the minimum number of matrices obtained by duplicating rows and columns of an identity matrix whose OR is the communication matrix, together with an entropy argument on $1$-chromatic rectangles; an improved inequality $\log\mathrm{bc}(A)\le ND^{\mathrm{Eq}}(A)+O(\log\log N)$ transfers the bound to non-deterministic Equality oracles.
What would settle it
Exhibit a deterministic Equality-oracle protocol for $\mathrm{RankOne}_n$ that asks $o(n)$ queries; equivalently, for the $N=n^2$-bit formulation, one that asks $o(\sqrt{N})$ queries. The theorems here predict that no such protocol exists; alternatively, computing $\gamma_2(\mathrm{RankOne}_n)$ for growing $n$ and finding growth far below $2^{\Omega(n)}$ would undercut the analytic proof.
Extended reading notes
Core claim
The central claim, Theorem 1, is that $\mathrm{BPP}^0\not\subseteq P^{\mathrm{Eq}}$: there exists $F:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ with $R(F)=O(1)$ and $D^{\mathrm{Eq}}(F)=\Theta(\sqrt{n})$. The witnessing function is $\mathrm{RankOne}_n$, defined on matrices $A,B\in\mathbb{F}_2^{n\times n}$ by $\mathrm{RankOne}_n(A,B)=1$ iff $A\oplus B$ has rank at most one. The paper proves $R(\mathrm{RankOne}_n)=O(1)$ by exhibiting a constant-depth randomized parity decision tree, and proves $D^{\mathrm{Eq}}(\mathrm{RankOne}_n)=\Theta(n)$ by two routes: an analytic route showing $\gamma_2(\mathrm{RankOne}_n)=2^{\Theta(n)}$ and applying the inequality $\frac12\log\gamma_2(M)\le D^{\mathrm{Eq}}(M)$, and a combinatorial route showing the blocky cover number $\mathrm{bc}(\mathrm{RankOne}_n)=2^{\Omega(n)}$, which after an improved inequality yields the same bound even for non-deterministic Equality-oracle protocols. The same machinery yields an $\Omega(n/\log n)$ lower bound on queries to any constant-$k$ Hamming Distance oracle, a function with $\lVert \hat f\rVert_{1,1/3}=O(1)$ but $\lVert \hat f\rVert_1=2^{\Omega(n)}$, a constant-depth randomized parity decision tree whose deterministic parity decision tree has size $2^{\Omega(n)}$, and $ND^{\mathrm{Eq}}(\mathrm{IIP}^n_3)=\Theta(n)$.
Load-bearing premise
The lower bound rests on previously established inequalities that turn a matrix measure—the $\gamma_2$-norm in the analytic proof or the blocky cover number in the combinatorial proof—into Equality-oracle cost; the paper computes the measures but does not prove the translations.
Editorial extensions
If this is right
- $\mathrm{BPP}^0\not\subseteq P^{\mathrm{Eq}}$: constant-cost randomized communication cannot be simulated with polylogarithmically many Equality queries.
- Equality oracles are far weaker than the $1$-Hamming Distance example suggests: $D^{\mathrm{Eq}}(\mathrm{HD}^n_1)=O(\log n)$ is not the general pattern for constant-cost problems.
- For every constant $k$, $D^{\mathrm{HD}_k}(\mathrm{RankOne}_n)=\Omega(n/\log n)$, giving a simpler and quantitatively stronger non-reducibility to the $k$-Hamming Distance hierarchy.
- There is an XOR function with approximate spectral norm $O(1)$ but exact spectral norm $2^{\Omega(n)}$, and a randomized parity decision tree of constant depth whose deterministic parity decision tree has size $2^{\Omega(n)}$.
- $ND^{\mathrm{Eq}}(\mathrm{IIP}^n_3)=\Theta(n)$, removing the logarithmic factor from earlier non-deterministic Equality-oracle lower bounds.
Reading between the lines
- A natural next test is whether the same $\Theta(\sqrt{N})$ barrier (in input bits $N=n^2$) appears for other natural oracles, such as Greater-Than or Hamming Distance for growing $k$; the paper proves the barrier only for Equality and for constant-$k$ Hamming Distance.
- Because the blocky-cover proof already handles non-deterministic Equality-oracle protocols, it is plausible that zero-error or bounded-error randomized Equality-oracle protocols also need $\Omega(n)$ queries on $\mathrm{RankOne}_n$; this strengthening is not stated in the paper.
- The constant-depth randomized parity decision tree for rank-one is essentially a random $2\times2$ submatrix sketch; the same sketch may give constant-cost protocols for other matrix predicates, while the oracle lower bound may depend on the combinatorial rectangle structure of the predicate.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the communication problem RankOne_n, in which Alice and Bob hold n x n matrices A and B over F_2 and must decide whether A xor B has rank at most 1. The main theorem states that this problem, viewed as a problem on n^2 input bits, has randomized communication cost O(1) but deterministic Equality-oracle cost Theta(n), i.e. Theta(sqrt N) in terms of the number N of input bits. The proof has two parts. The analytic part gives a randomized parity decision tree of constant depth for the rank-one predicate, an O(n)-query Equality-oracle protocol, and a lower bound on the gamma_2 norm via a Holder-inequality argument, yielding D^Eq(RankOne_n) = Omega(n). The combinatorial part attempts to prove an Omega(n) lower bound even for non-deterministic Equality-oracle protocols using blocky covers. The paper also derives consequences for the k-Hamming Distance hierarchy, for parity decision trees, for approximate versus exact spectral norm, and for the Integer Inner Product function.
Significance. If the proofs are correct, the paper settles a natural question from Hatami--Hatami's survey: constant-cost randomized protocols cannot be efficiently derandomized using Equality oracles. The analytic proof is elegant and largely self-contained, and Theorem 3 is a very simple and convincing constant-cost protocol. The separation BPP^0 not subset of P^Eq would improve previous results and give a simpler proof of the recent STOC 2025 result on the k-Hamming Distance hierarchy. The additional non-deterministic separation and the corollaries on parity decision trees and spectral norm are also valuable. However, the combinatorial proof of the non-deterministic lower bound is not valid as written, and the central lower bound depends on an external inequality whose compatibility with the paper's oracle model should be stated explicitly. The analytic main result is still likely correct, but the manuscript currently overclaims the non-deterministic strengthening.
major comments (2)
- [Section 4, Claim 11] The proof of Claim 11 does not establish the claimed entropy bound. From H(ell^A, r^A) >= (2-10^{-2})n, the average of H(ell^A_i, r^A_i, ell^A_{i+1}, r^A_{i+1}) over odd i is at least 2(2-10^{-2}) = 3.98, but the text instead asserts only that 2/3 of the pairs have entropy at least 2-3*10^{-2} = 1.97, and then jumps to H(ell^A_1, r^A_1, ell^A_2, r^A_2) >= 2(2-10^{-2}) > log 15. The latter inequality is not a consequence of the former, and it is not enough to consider the A-tuple alone: a common index i must be found for both the A- and B-tuples, for instance by averaging the sum of the two pair entropies. Since Theorem 9 uses Claim 11 to contradict Claim 10, the non-deterministic lower bound and the abstract/corollary claims that depend on it are not supported as written. A corrected averaging argument may repair this, but the current proof is incomplete.
- [Section 3, Eq. (2)] The lower bound of Theorem 1 is entirely dependent on the cited inequality 1/2 log gamma_2(M) <= D^Eq(M) from [9]. Section 5.1, Remark 12 later specifies that in the paper's oracle model the inputs to an Equality query may have arbitrary length. The authors should state explicitly that Eq. (2) is valid for exactly this model, or give the precise statement from [9]. If the cited inequality was proved only for a model in which query strings are bounded by the input length, the central separation would not transfer to the model used in this paper.
minor comments (3)
- [Section 3, Theorem 6, Eq. (3)] The proof says there are 2^{2n} rank-1 matrices, but the exact number is (2^n-1)^2+1 = 2^{2n}-2^{n+1}+2 because the all-zero matrix has multiple rectangle representations. This changes the Frobenius norm by only a 1-O(2^{-n}) factor and does not affect the 2^{Omega(n)} lower bound, but the count should be corrected.
- [Section 3, General position paragraph] In the argument bounding the number of triples in general position, the text states that R_1 xor R_2 xor R_3 = a*b^T. With the notation as written, the identity should be b*a^T (or one of the two vectors should be transposed consistently). The counting conclusion is unaffected because there are still at most 9 possible matrices R_3.
- [Section 5.1, Corollary 2 proof] The phrase '2n2 x 2n2 matrices' should read '2^{n^2} x 2^{n^2} matrices'; several other occurrences of 'n2' and '2n' appear to have lost their superscripts in the text.
Circularity Check
No significant circularity: the lower bound is an independent gamma_2 computation plus an external inequality; self-citations are not load-bearing.
full rationale
I find no circularity. The central claim (Theorem 1) rests on two independent ingredients: Theorem 3 gives a self-contained constant-depth randomized parity decision tree for RankOne_n (hence R(RankOne_n)=O(1)), and Theorem 6 gives a self-contained counting lower bound gamma_2(RankOne_n)=2^{Omega(n)}. The lower bound on D^Eq then follows by the cited inequality (2), (1/2) log gamma_2(M) <= D^Eq(M), from Hambardzumyan-Hatami-Hatami; this is an external, parameter-free theorem whose assumptions do not include the target result, so relying on it is not circular. The upper bound D^Eq(RankOne_n)=O(n) is proved directly in Proposition 4. The combinatorial proof of the NPEq strengthening uses the blocky-cover inequalities of Pitassi-Shirley-Shraibman and a self-contained Appendix lemma; again no step defines or fits the target quantity in terms of itself. The only self-citations occur in the applications: Corollary 2 invokes [8, Prop 4.1] (a theorem by an overlapping author) to bound D^Eq of HD_k submatrices. That cited theorem is an independent published result, is not derived from RankOne_n or from Theorem 1, and is not used in the proof of Theorem 1; hence it does not make the argument circular. Minor internal issues, such as the count of rank-at-most-one matrices in Theorem 6 being (2^n-1)^2+1 rather than 2^{2n} and the garbled entropy thresholds in Claim 11, are correctness and typographical concerns that do not change the asymptotic exponent in the analytic proof and are not instances of circular reasoning.
Assumptions & free parameters
assumptions (4)
- domain assumption Equation (2): ½ log γ2(M) ≤ D^Eq(M) for every boolean matrix M.
- standard math Lemma 5 (Hölder inequality corollary): γ2(M) ≥ (1/N) · ∥M∥_F^3 / sqrt(tr((M^T M)^2)).
- domain assumption Inequality (4): ND^Eq(A) ≤ log bc(A) ≤ O(ND^Eq(A) · log log N) for boolean A.
- domain assumption Theorem 14 from [8]: any N×N submatrix of HD_k^n has D^Eq cost O(k log log N).
Cite this review
Pith. "Pith review of Equality is Far Weaker than Constant-Cost Communication." pith.science (2026). https://pith.science/paper/7NBQ26H4
@misc{pith2026250711162,
author = {Pith},
title = {Pith review of: Equality is Far Weaker than Constant-Cost Communication},
year = {2026},
howpublished = {\url{https://pith.science/paper/7NBQ26H4}},
note = {Machine review of arXiv:2507.11162}
}
abstract
We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of Hatami and Hatami (SIGACT News 2024). It also gives a significantly simpler and quantitatively superior proof of the main result of Fang, G\"o\"os, Harms, and Hatami ( STOC 2025), that constant-cost communication does not reduce to the $k$-Hamming Distance hierarchy.
Reference graph
Works this paper leans on
-
[9]
Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami. Dimension-free bounds and structural results in communication complexity.Israel Journal of Mathematics, 253(2):555– 616, 2023.doi:10.1007/s11856-022-2365-8
-
[1]
A discrepancy lower bound for information complexity
Mark Braverman and Omri Weinstein. A discrepancy lower bound for information complexity. Algorithmica, 76:846–864, 2016.doi:10.1007/s00453-015-0093-8
-
[2]
Equality alone does not simulate randomness
Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals. Equality alone does not simulate randomness. InProceedings of the Computational Complexity Conference (CCC), pages 14–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2019.doi:10.4230/LIPIcs.CCC.2019.14
-
[3]
A lower bound on the trace norm of boolean matrices and its applications
Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley. A lower bound on the trace norm of boolean matrices and its applications. InProceedings of the Innovations in Theoretical Computer Science Conference (ITCS), pages 37–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2025.doi:10.4230/LIPIcs.ITCS.2025.37
-
[4]
Separation of the factorization norm and randomized communication complexity
Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley. Separation of the factorization norm and randomized communication complexity. InProceedings of the Computational Complexity Conference (CCC), pages 1–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2023.doi:10.4230/LIPIcs.CCC.2023.1
-
[5]
Tsun Ming Cheung, Hamed Hatami, Rosie Zhao, and Itai Zilberstein. Boolean functions with small approximate spectral norm.Discrete Analysis, 2024.doi:10.19086/da.122971
-
[6]
Sketching distances in monotone graph classes
Louis Esperet, Nathaniel Harms, and Andrey Kupavskii. Sketching distances in monotone graph classes. InApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 18–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2022.doi:10.4230/LIPIcs.APPROX/RANDOM.2022.18
-
[7]
Constant-cost communication does not reduce tok-Hamming Distance
Yuting Fang, Mika G¨ o¨ os, Nathaniel Harms, and Pooya Hatami. Constant-cost communication does not reduce tok-Hamming Distance. InProceedings of the ACM SIGACT Symposium on Theory of Computing (STOC), 2025.doi:10.48550/arXiv.2407.20204
Show all 23 references
-
[8]
No complete problem for constant-cost randomized communication
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, and Pooya Hatami. No complete problem for constant-cost randomized communication. InProceedings of the ACM SIGACT Symposium on Theory of Computing (STOC), 2024.doi:10.48550/arXiv.2404.00812
-
[10]
Universal communication, universal graphs, and graph labeling
Nathaniel Harms. Universal communication, universal graphs, and graph labeling. InPro- ceedings of the Innovations in Theoretical Computer Science Conference (ITCS), volume 151, page 33. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020.doi:10.4230/LIPIcs.ITCS.2020. 33
2020 doi
-
[11]
Better boosting of communication oracles, or not
Nathaniel Harms and Artur Riazanov. Better boosting of communication oracles, or not. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2024.doi:10.4230/LIPIcs.FSTTCS.2024.25
2024 doi
-
[12]
Randomized communication and implicit graph representations
Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev. Randomized communication and implicit graph representations. InProceedings of the ACM SIGACT Symposium on Theory of Computing (STOC), 2022.doi:10.1145/3519935.3519978. 14
2022
-
[13]
Randomized communication and implicit representa- tions for matrices and graphs of small sign-rank
Nathaniel Harms and Viktor Zamaraev. Randomized communication and implicit representa- tions for matrices and graphs of small sign-rank. InProceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1810–1833. SIAM, 2024.doi:10.1137/1.9781611977912.72
2024 doi
-
[14]
Guest column: Structure in communication complexity and constant-cost complexity classes.ACM SIGACT News, 55(1):67–93, 2024.doi:10.1145/ 3654780.3654788
Hamed Hatami and Pooya Hatami. Guest column: Structure in communication complexity and constant-cost complexity classes.ACM SIGACT News, 55(1):67–93, 2024.doi:10.1145/ 3654780.3654788
2024
-
[15]
Cambridge University Press, 1996
Eyal Kushilevitz and Noam Nisan.Communication complexity. Cambridge University Press, 1996
1996
-
[16]
The communication complexity of threshold gates.Combinatorics, Paul Erdos is Eighty, 1(301-315):6, 1993
Noam Nisan. The communication complexity of threshold gates.Combinatorics, Paul Erdos is Eighty, 1(301-315):6, 1993
1993
-
[17]
The strength of equality oracles in communication
Toniann Pitassi, Morgan Shirley, and Adi Shraibman. The strength of equality oracles in communication. InProceedings of the Innovations in Theoretical Computer Science Conference (ITCS), pages 89–1. Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 2023.doi:10.4230/LIPIcs. IT...
2023 doi
-
[18]
Cambridge University Press, 2020
Anup Rao and Amir Yehudayoff.Communication Complexity: and Applications. Cambridge University Press, 2020
2020
-
[19]
Boolean functions with small spectral norm, revisited.Mathematical Proceedings of the Cambridge Philosophical Society, 167(2):335–344, 2019.doi:10.1017/S030500411800035X
Tom Sanders. Boolean functions with small spectral norm, revisited.Mathematical Proceedings of the Cambridge Philosophical Society, 167(2):335–344, 2019.doi:10.1017/S030500411800035X
2019 doi
-
[20]
The communication complexity of approximat- ing matrix rank
Alexander Sherstov and Andrey Storozhenko. The communication complexity of approximat- ing matrix rank. InProceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pages 433–462. IEEE, 2024.doi:10.1109/FOCS61266.2024.00035
2024
- [21]
- [22]
-
[23]
The communication complexity of addition.Combinatorica, 35(6):703–747, 2015.doi:10.1007/s00493-014-3078-3
Emanuele Viola. The communication complexity of addition.Combinatorica, 35(6):703–747, 2015.doi:10.1007/s00493-014-3078-3. 15
2015 doi
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.