{"id":"7a7604d1-25b3-41c4-8baf-c85fa1866705","arxiv_id":"2507.11162","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"There is a communication problem with constant randomized cost that requires Ω(√n) deterministic queries to an Equality oracle, so constant-cost randomness cannot be efficiently derandomized by equality checks.","lead":"Alice and Bob each hold a large binary matrix and must decide whether the coordinate-wise sum of the two matrices has rank at most one. This paper shows that while a constant number of random bits lets them solve the task, any deterministic protocol using a perfect equality-checking oracle needs about the square root of the input length in queries.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: Theorem 1 is supported by a sound analytic proof; the cited inequality (2) is the only external dependency, and the manuscript's internal errors are asymptotically immaterial.","rationale":"The reader's weakest_assumption identifies Equation (2) as the key external dependency, and that is indeed the only external assumption in the analytic proof of Theorem 1. However, relying on a cited theorem is standard practice and not by itself a defect, especially since the theorem is from a well-known paper and is stated in essentially this form. The reader's CONDITIONAL verdict is based on minor text inaccuracies, and I confirm those: the number of rank-1 matrices in Theorem 6 should be (2^n - 1)^2 + 1, and the entropy thresholds in Claim 11 are garbled. Neither issue changes the asymptotic conclusion of Theorem 1. The counting of triples in Theorem 6 is otherwise consistent after absorbing the lower-order correction. The combinatorial proof's garbled Claim 11 affects only the optional non-deterministic lower bound and Corollary 2, not the central separation. I therefore see no reason to move the verdict; the paper is acceptable modulo minor corrections.","tokens_in":13785,"tokens_out":30466,"duration_ms":367228,"concrete_test":"Check the original statement in Hambardzumyan, Hatami, and Hatami to confirm that the inequality (1/2) log gamma_2(M) <= D^Eq(M) is proved for the same D^Eq model as Remark 12, i.e., with unbounded query-input size. If it is, Theorem 1 is verified; if the cited theorem only covers bounded-length queries, an independent proof of (2) for the unbounded model is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I do not find a load-bearing flaw in the central claim. Theorem 1 is established by Theorem 6 plus Equation (2), a cited result from Hambardzumyan, Hatami, and Hatami; the paper is not required to re-prove that result. The internal count of rank-1 matrices in Theorem 6 is slightly off: the exact number is (2^n - 1)^2 + 1 rather than 2^{2n}. This changes the Frobenius norm by only a 1 - o(1) factor and does not affect the 2^{Omega(n)} lower bound on gamma_2. The garbled entropy thresholds in Claim 11 concern only the optional combinatorial strengthening and Corollary 2, not Theorem 1 itself. Thus the main separation BPP^0 not subset of P^Eq stands. The one external assumption worth verifying is that Equation (2) applies to the D^Eq model of Remark 12, in which Equality-query inputs may have arbitrary length.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":13958,"tokens_out":35554,"duration_ms":418339,"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":[{"comment":"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":"Section 4, Claim 11"},{"comment":"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.","section":"Section 3, Eq. (2)"}],"minor_comments":[{"comment":"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":"Section 3, Theorem 6, Eq. (3)"},{"comment":"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":"Section 3, General position paragraph"},{"comment":"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.","section":"Section 5.1, Corollary 2 proof"}],"recommendation":"major_revision","confidential_remarks":"The central analytic separation is believable and important, and the main proof is likely fixable. The main risk is that the manuscript currently overclaims the non-deterministic strengthening, and the compatibility of Eq. (2) with the arbitrary-length oracle model should be clarified. I recommend requesting a revision that repairs Claim 11 or explicitly removes the unsupported non-deterministic claims, and that states the exact model for Eq. (2)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The central claim is true: there is an explicit communication problem with constant randomized cost and Θ(√n) Equality-oracle lower bound (Θ(√N) on N-bit inputs), resolving a question from the Hatami–Hatami survey and improving the previous logarithmic separation to square-root. The analytic proof via γ2-norm is clean and sound. The counting error flagged in Theorem 6 is real but immaterial: the exact number of rank-1 matrices including zero is (2^n−1)^2+1 = 2^{2n}−2^{n+1}+2, not 2^{2n}. This changes the Frobenius norm by a 1−O(2^{-n}) factor and leaves γ2(RankOne_n)=2^{Θ(n)} intact.\n\nThe combinatorial proof is a different story. Claim 10 is fine, but Claim 11's entropy thresholds appear garbled: the expression \"2^{-3}·10^{-2}\" cannot be what the argument needs, since the conclusion requires a constant above log 15 and the surrounding derivation actually yields a bound like 2(2−10^{-2}). This looks like a typesetting slip, but it makes that section genuinely hard to follow. Since the main theorem does not rely on the combinatorial proof, this is a minor issue, but Corollary 19 and the ND^Eq strengthening depend on it, so it should be rewritten.\n\nThe dependence on Eq. (2) from Hambardzumyan–Hatami–Hatami is a standard cited theorem, not a gap. The paper also gives a genuinely simpler proof of the Fang–Göös–Harms–Hatami STOC 2025 result and answers a question about parity decision trees. The corollaries on spectral norm and non-deterministic Equality oracles are nice, and the paper is well-motivated with concrete examples.\n\nFor a communication complexity reader, this is a significant, well-executed advance. The typos are unfortunate but should not sink it. A careful referee will want the combinatorial proof cleaned up, but the main result deserves publication. Send it to a good conference; I would accept after minor revisions, and I'd be glad to discuss it at the next reading group.","headline":"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.","tokens_in":14516,"tokens_out":4643,"would_cite":true,"duration_ms":50340,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q11"],"pacs":[],"model":"deepseek-v4-flash","headline":"There is a constant-cost randomized communication problem that any deterministic Equality-oracle protocol needs $\\Theta(\\sqrt{n})$ queries to solve.","keywords":["communication complexity","Equality oracle","constant-cost randomized communication","rank-one matrices","gamma-2 norm","blocky cover","parity decision tree","k-Hamming Distance hierarchy"],"falsifier":"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.","tokens_in":13557,"feed_emoji":"🎲","tokens_out":13356,"duration_ms":143579,"temperature":0.7,"pith_summary":"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.","feed_headline":"Constant-cost randomness beats Equality oracles: Θ(√n) gap","feed_subtitle":"A rank-one matrix problem needs Θ(√n) Equality checks despite an O(1) randomized protocol.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["$\\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."],"supporting_citations":[{"why":"Supplies the inequality $\\frac12\\log\\gamma_2(M)\\le D^{\\mathrm{Eq}}(M)$ that converts the $\\gamma_2$-norm lower bound for $\\mathrm{RankOne}_n$ into an Equality-oracle lower bound, plus the XOR identity $\\gamma_2(F)=\\lVert \\hat f\\rVert_1$ used in the spectral-norm corollaries.","marker":"[9]"},{"why":"Supplies Lemma 5, the Hölder-inequality bound on $\\gamma_2$, and the maxrect theorem used for $\\mathrm{IIP}^n_3$ in the non-deterministic lower bound.","marker":"[3]"},{"why":"Defines the blocky cover number and the inequalities connecting it to non-deterministic Equality-oracle cost, which the paper improves in Lemma 8.","marker":"[17]"},{"why":"Supplies Proposition 4.1 bounding $D^{\\mathrm{Eq}}$ of submatrices of $\\mathrm{HD}^n_k$ by $O(k\\log\\log N)$, which transfers the $\\mathrm{RankOne}_n$ lower bound to $k$-Hamming Distance oracles.","marker":"[8]"}],"fun_headline_variants":["Randomness with O(1) cost needs √n Equality queries","Equality oracles can't match constant-cost randomness","Θ(√n) gap: constant randomness vs Equality queries","RankOne problem: O(1) randomized, √n deterministic"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Randomness with O(1) cost needs √n Equality queries","Equality oracles can't match constant-cost randomness","Θ(√n) gap: constant randomness vs Equality queries","RankOne problem: O(1) randomized, √n deterministic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000596,"raw_usage":{"total_tokens":2834,"prompt_tokens":1036,"completion_tokens":1798,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":1727}},"tokens_in":652,"tokens_out":1798,"duration_ms":18231,"temperature":1.0,"reasoning_tokens":1727,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:18:05.887564+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}