Pith. sign in

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 →

arxiv 2507.11162 v1 pith:7NBQ26H4 submitted 2025-07-15 cs.CC

classification cs.CC MSC 68Q11
keywords communicationcomplexityEqualityoracleconstant-costrandomizedrank-onematricesgamma-2normblockycoverparitydecisiontreek-HammingDistancehierarchy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that simple hashing cannot replace public randomness even for constant-cost communication: there is a problem that any randomized protocol solves with $O(1)$ communication, yet any deterministic protocol using an Equality oracle must make $\Theta(\sqrt{n})$ queries on $n$-bit inputs. The witness is $\mathrm{RankOne}_n$, in which Alice and Bob hold $n\times n$ matrices over $\mathbb{F}_2$ and decide whether their sum has rank at most one. A constant-depth randomized parity decision tree solves $\mathrm{RankOne}_n$, while both the analytic proof (via the $\gamma_2$-norm) and the combinatorial proof (via blocky covers) give $D^{\mathrm{Eq}}(\mathrm{RankOne}_n)=\Theta(n)$, i.e. $\Theta(\sqrt{N})$ when the input has $N=n^2$ bits. The paper concludes that $\mathrm{BPP}^0\not\subseteq P^{\mathrm{Eq}}$, so constant-cost randomized protocols are not efficiently derandomized by Equality oracles.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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)
  1. [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.
  2. [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)
  1. [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.
  2. [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.
  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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 4 assumptions · 0 invented entities

The main theorem uses two imported inequalities: Eq. (2) from [9] and Lemma 5 from [3]. The combinatorial proof additionally uses the blocky cover framework from [17]. No free parameters are fitted to data; the constants in the entropy argument are chosen for the proof and are not empirical. No new entities are postulated.

assumptions (4)
  • domain assumption Equation (2): ½ log γ2(M) ≤ D^Eq(M) for every boolean matrix M.
    Imported from [9]; this is the bridge that converts the γ2 lower bound into the Equality-oracle lower bound in Theorem 6. The paper does not prove it.
  • standard math Lemma 5 (Hölder inequality corollary): γ2(M) ≥ (1/N) · ∥M∥_F^3 / sqrt(tr((M^T M)^2)).
    Imported from [3]; used to lower bound γ2(RankOne_n). It is a corollary of Hölder's inequality.
  • domain assumption Inequality (4): ND^Eq(A) ≤ log bc(A) ≤ O(ND^Eq(A) · log log N) for boolean A.
    Imported from [17]; used in the combinatorial proof of Theorem 9 and improved in Lemma 8 to remove the log log factor.
  • domain assumption Theorem 14 from [8]: any N×N submatrix of HD_k^n has D^Eq cost O(k log log N).
    Used in the proof of Corollary 2 to replace HD_k oracle queries by Equality queries. The paper cites [8] for it.

how reviews work

0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 9 canonical work pages

  1. [9]

    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

    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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [5]

    Boolean functions with small approximate spectral norm.Discrete Analysis, 2024.doi:10.19086/da.122971

    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

  7. [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

  8. [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
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [15]

    Cambridge University Press, 1996

    Eyal Kushilevitz and Noam Nisan.Communication complexity. Cambridge University Press, 1996

  8. [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

  9. [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...

  10. [18]

    Cambridge University Press, 2020

    Anup Rao and Amir Yehudayoff.Communication Complexity: and Applications. Cambridge University Press, 2020

  11. [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

  12. [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

  13. [21]

    The discrepancy of greater-than.arXiv preprint arXiv:2309.08703, 2023.doi:10.48550/ARXIV.2309.08703

    Srikanth Srinivasan and Amir Yehudayoff. The discrepancy of greater-than.arXiv preprint arXiv:2309.08703, 2023.doi:10.48550/ARXIV.2309.08703

  14. [22]

    Factorization norms and Zarankiewicz problems.arXiv preprint arXiv:2502.18429, 2025.doi:10.48550/arXiv.2502.18429

    Istv´ an Tomon. Factorization norms and Zarankiewicz problems.arXiv preprint arXiv:2502.18429, 2025.doi:10.48550/arXiv.2502.18429

  15. [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

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.