{"id":"114093a4-9391-4220-829c-5f5227e4e2dd","arxiv_id":"2502.01900","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For the p-biased hypercube, a k-query linearity test works in the 1% regime if and only if k is at least 1 + 1/min{p,1-p}, up to an odd-k boundary case involving cyclic characters.","lead":"This paper characterizes when a k-query linearity test works on a biased Boolean hypercube in the low-agreement, 1% regime. It shows the test succeeds precisely when the sampling distribution has a pairwise independent coordinate, up to one unresolved odd-k boundary case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The positive half of Theorem 5 rests on Theorem 33, whose Section 7 proof is an outline; Step 4's invariance principle is invoked for functions containing biased characters χ_S, whose influences are not small, so the BKM transfer is not automatic and needs a new argument.","rationale":"The reader's conditional verdict is exactly right. The negative half is self-contained and convincing. The positive half is one black-box chain away: Theorem 33 is a nontrivial generalization of BKM23b to all k and p, and the sketch does not verify that the invariance principle applies to characters of the biased hypercube. I emphasize that this is a missing proof, not a claimed counterexample; the theorem may be true. If the Step 4 derivation can be completed, the paper's characterization likely stands. Therefore I do not move the verdict: it remains conditional on the missing proof.","tokens_in":25652,"tokens_out":14880,"duration_ms":160143,"concrete_test":"Specialize to the smallest instance outside BKM23b: k=5, p=1/4, with ν from Lemma 28 (threshold case, full even-weight support). Run Section 7 Steps 1–3 explicitly for this ν and an arbitrary f, and write out Equation (2) with functions φ_i=χ_{S_i}g_i. Then test Step 4: compute max_j Inf_{μ_p}(φ_i). For every nonempty S_i, this maximum is at least 2p(1−p)=3/8. Verify whether the cited invariance principle, stated with all hypotheses, applies to such φ_i; if not, exhibit the additional argument that justifies replacing X by the Gaussian Z while preserving the lower bound. Completing this derivation for k=5, p=1/4 would settle whether the positive direction is more than a conjecture.","verdict_should_be":"UNCHANGED","load_bearing_attack":"All positive cases in Theorem 5 route through Theorem 33. Section 7 is explicitly 'a rough outline (skipping many technical points)', and the decisive g≡1 conclusion depends on Step 4. Step 4 asserts that an MOO/Mossel invariance principle lets one replace the expectation over X∼ν^⊗n in Equation (2) by an expectation over Z∼N(0,Σ)^⊗n, where the integrand contains χ_{S_{j_i}}(X_i)g_{j_i}(X_i). This is not a standard application: under μ_p, every coordinate j∈S_i has influence 2p(1−p), a constant, and for p near 1/2 this is about 1/2. The paper does not state which invariance theorem is used, nor does it verify low-influence or bounded-degree hypotheses, nor does it give the promised 'extra structure' on the S_{j_i}. If this step cannot be supplied, the existence half of Theorem 5 items 1 and 2 is unsupported. The negative direction, Theorem 24, is proved in detail and is not affected by this concern.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies k-query linearity tests Lin(ν) over the p-biased hypercube in the 1% regime, where ν is a distribution on even-weight vectors in {0,1}^k with each marginal μ_p. The main theorem (Theorem 5) claims a near-complete characterization: for k > 1 + 1/min{p,1-p} there exists ν such that Lin(ν) works in the 1% regime, and for k < 1 + 1/min{p,1-p} no such test works. The positive direction is derived from a claimed generalization (Theorem 33) of the BKM23b linearity-testing theorem, whose proof is only outlined in Section 7; the corner case p=1-1/(k-1) with odd k is treated separately using Theorem 31, whose proof is deferred to overlapping-author preprints. The negative direction (Theorem 24) is proved in detail using a Gaussian counterexample, a polynomial-construction lemma, and a rounding argument.","tokens_in":25861,"tokens_out":9908,"duration_ms":94959,"significance":"If the positive direction can be made rigorous, this is a significant contribution: it gives a clean, essentially complete characterization of when k-query biased linearity tests work in the 1% regime, extending BKM23b from k=4 to all k and p. The negative theorem (Theorem 24) is self-contained and appears sound; the Gaussian-variant proof in Section 3 and the explicit distribution constructions in Lemmas 28 and 29 are valuable, falsifiable building blocks. The trade-off proposition (Propositions 25 and 27) is a simple and elegant result. However, the paper's main positive claim is conditional on a proof sketch and on several unverified technical transfers, so the significance of the manuscript in its current form is substantially weakened.","major_comments":[{"comment":"The invariance principle step is not justified as written. The functions being transferred are of the form χ_{S_{j_i}}(X_i)g_{j_i}(X_i). Under the p-biased measure, a character χ_S has influence 4p(1-p) on each coordinate in S, which is a constant independent of n (equal to 1 for p=1/2), so the low-influence hypothesis of the cited invariance principles ([MOO10, Mos10, Mos20]) is not satisfied. The manuscript states that 'some extra structure on S_{j_i}'s is needed' but does not state or prove that structure. Consequently, the approximation E_{(X_1,...,X_k)∼ν^{⊗n}}[∏ χ_{S_{j_i}}(X_i)g_{j_i}(X_i)] ≈ E_{(Z_1,...,Z_k)∼N(0,Σ)^{⊗n}}[...] is unsupported. This step is the bridge to the g≡1 conclusion in Theorem 33 and thus to the positive half of Theorem 5 items 1 and 2.","section":"Section 7, Step 4"},{"comment":"The proof of Theorem 33 is explicitly 'a rough outline (skipping many technical points)'. Step 2 imports Theorem 1.1 of [BKM23b] as a black box, and Step 3 asserts that the list-decoding machinery of [BKM23b, Sections 4.2–4.3] extends to arbitrary k and p. Since Theorem 5 items 1 and 2 are derived entirely from Theorem 33, the main positive claim of the paper is not proven in this manuscript. The authors should either provide complete proofs of these extensions or explicitly state the paper as conditional on the full version of the proof.","section":"Section 7, Steps 2–3"},{"comment":"Theorem 31 is stated as a theorem of the paper, but its proof is deferred entirely: 'The result follows from the work of Bhangale, Khot, Liu and Minzer [BKLM24a, BKLM24b], and we omit the details.' These are overlapping-author preprints that are not yet published, and no specific theorem in them is cited. Since Theorem 31 is used to justify the claim about correlation with Z/(k-1)Z characters in the corner case, this is a substantial missing proof. Please either prove the statement or clearly mark it as a conjecture or as a result proved elsewhere.","section":"Section 6.1, Theorem 31"},{"comment":"The proof of Lemma 28 states 'for brevity, we omit the verification of the above properties'. The vector q must satisfy three equations (total probability 1, marginal p, pairwise independence p^2) and lie in [0,1]^{s+1} with certain entries zero; the formulas are given in four cases. The verification of these equations is load-bearing for Proposition 27 and therefore for the existence of pairwise independent distributions used in Theorem 5. Please include the verification (or at least the nonnegativity and the three equations) for each case.","section":"Lemma 28"}],"minor_comments":[{"comment":"The abstract says 'if k ≥ 1 + 1/p' while Theorem 5(1) says 'for every integer k > 1 + 1/min{p,1-p}'. Also, the abstract restricts to p ≤ 1/2 but the theorem treats p ∈ (0,1). Please make the statements consistent.","section":"Abstract and Theorem 5"},{"comment":"The symbol μ is used for the uniform distribution on the BLR support, which clashes with the notation μ_p for the p-biased measure. Please use a distinct symbol, e.g., μ_BLR.","section":"Section 7, Step 1"},{"comment":"The condition span_{F2}(supp(ν)) = {x ∈ {0,1}^k : Σ x_i = 0 mod 2} is introduced without explanation. It is used in Step 3 of the proof of Theorem 33; please add a sentence explaining its role.","section":"Definition 32"},{"comment":"The existence of a function f with all correlations o_n(1) is asserted without proof, with a reference to 'an argument similar to the one at the end of Section 4.2'. Since this case deals with tests that are vacuous after cancellation, a brief justification (e.g., random function plus Hoeffding/union bound) would improve clarity.","section":"Theorem 5, item 3 case (a)"},{"comment":"The paper cites 'Theorem 1.1 in [BKM23b]', but the reference list entry for [BKM23b] does not identify which result is Theorem 1.1. Please provide a more precise reference or the full statement.","section":"Section 7, Step 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's positive direction is almost entirely conditional on overlapping-author preprints [BKM23b] and [BKLM24a/b], and the proof of the central Theorem 33 is only an outline. This is a dependency, not a circularity, but the journal should weigh whether the extent of black-boxing is acceptable. The negative theorem (Theorem 24) is a solid, self-contained contribution that would be publishable on its own. If the journal is willing to accept a paper with a central proof sketch, this is borderline; otherwise a full proof of Theorem 33 is required."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The genuinely new and solid part is the negative direction. Theorem 8/24 shows that if no coordinate of ν is pairwise independent, then Lin(ν) accepts some function with constant probability that has vanishing correlation with every F2 character. The proof is self-contained: build a Gaussian counterexample, convert via CLT, round to Boolean when no pair of coordinates is almost surely equal. It also answers the open question from BKM23b about whether pairwise independence is necessary — it is.\n\nThe positive direction is a different story. The existence half of the main characterization (Theorem 5 items 1 and 2) rests on Theorem 33, which the paper explicitly labels as a rough outline with many technical points skipped. Step 4 of that outline invokes an invariance principle to pass from ν⊗n to Gaussian, but the integrand contains biased characters χ_S, whose influences are constant rather than small. The paper does not state which invariance theorem is being used or verify its hypotheses. This is a real gap, not a cosmetic one. The stress-test note has it right: if Step 4 cannot be supplied, the existence half is unsupported. There is also Step 3, which imports BKM23b's list-decoding machinery as a black box, and Step 2 imports the direct product theorem. Those are dependencies on overlapping-author prior work, which is not circular, but it does mean the paper itself does not contain a proof of its main positive claims.\n\nThe corner case for odd k ≥ 5 and p = 1 − 1/(k−1) is handled by Theorem 31, whose proof is entirely deferred to BKLM24a/b, and the conclusion is correlation with Z/(k−1) characters, not F2-linearity. So the abstract's 'if and only if' is stronger than what is actually established. The alternative test proposed in Section 6.1 only accepts affine functions with a sign, not all linear functions, which is a real limitation of that fix.\n\nOn the positive side, the query-bias tradeoff (Proposition 11) is clean, and the explicit distributions in Lemma 28 are explicit enough that the omitted verification is a routine calculation, not a hole. The negative construction is a genuinely new technique.\n\nBottom line: this is a serious paper with one fully proved half and one half that is still a program. I would send it to a referee, but the referee should be told that the positive half is conditional until Theorem 33 has a complete proof or a pointer to a complete version. If this is meant for a conference, it might be acceptable as a conditional announcement, but the abstract's claim should be softened.","headline":"The negative half is new and solid; the positive half is a plausible but still sketchy extension of BKM23b, so the abstract's iff is a bit ahead of the proofs.","tokens_in":26404,"tokens_out":2183,"would_cite":true,"duration_ms":22264,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Biased linearity tests succeed past a sharp query threshold.","keywords":["p-biased hypercube","linearity testing","1% regime","pairwise independence","query complexity","Boolean functions","property testing","Fourier analysis"],"falsifier":"Fix $p=0.1$ and $k=10$ (below the threshold $1+1/p = 11$), construct the explicit function from Theorem 24 as $f(x)=h((\\sum_j x_j - np)/\\sqrt{np(1-p)})$ using the Gaussian counterexample from Proposition 19, and numerically verify that for $\\nu \\in D(p,10)$ the acceptance expectation stays above a constant while the maximum correlation with every linear character $\\chi_S$ decays with $n$; if the decay fails, the negative direction of the characterization is wrong.","tokens_in":25410,"feed_emoji":"🎯","tokens_out":13126,"duration_ms":120487,"temperature":0.7,"pith_summary":"The paper determines, for every bias $p \\in (0,1)$ and every integer $k$, whether a $k$-query linearity test over the $p$-biased hypercube can work in the 1% regime: functions that pass the test with constant advantage must have constant correlation with some linear function. The answer is controlled by a threshold: tests exist when $k \\geqslant 1 + 1/\\min\\{p,1-p\\}$ (with a few boundary cases) and fail when $k$ is smaller. The dividing line, in the family of distributions used by these tests, is a pairwise-independence condition: one coordinate of the sampled $k$-tuple must be independent of all the others. The negative half constructs explicit counterexamples from Gaussian limits, showing the non-existence of good tests below the threshold is robust, not an artifact of the construction.","feed_headline":"Exact query threshold found for biased linearity tests","feed_subtitle":"The divider is whether the test's distribution has a pairwise independent coordinate.","key_machinery":"The load-bearing object is a distribution $\\nu \\in D(p,k)$ — a distribution on even-weight $k$-bit strings with $p$-biased marginal in every coordinate — and specifically whether some coordinate of $\\nu$ is pairwise independent, meaning $E[X_i X_j] = p^2$ for all $j \\neq i$. The test $\\mathrm{Lin}(\\nu)$ samples $X_1,\\dots,X_k \\sim \\nu^{\\otimes n}$, queries $f$ at those points, and accepts iff $\\prod_i f(X_i)=1$. The paper proves two structural results about this object: a generalized linearity-testing theorem (Theorem 33) showing that if $\\nu$ contains a copy of the classical three-query uniform linearity subtest and has a pairwise independent coordinate, then any $f$ that passes with constant advantage is close to a linear character; and a converse theorem (Theorem 24) constructing, from any $\\nu$ without a pairwise independent coordinate, a bounded function accepted with constant probability that has no linear correlation, via a Gaussian-variable construction using orthogonal Hermite polynomials and a symmetrized-polynomial lemma. The threshold $k = 1 + 1/\\min\\{p,1-p\\}$ is exactly where such pairwise-independent distributions exist (Propositions 25 and 27).","core_discovery":"The central claim (Theorem 5) is a near-complete characterization of $k$-query linearity testing over the $p$-biased hypercube in the 1% regime, for tests built from any distribution $\\nu \\in D(p,k)$ on even-parity $k$-bit strings with each coordinate $p$-biased. For $k > 1 + 1/\\min\\{p,1-p\\}$ there is a distribution for which the test $\\mathrm{Lin}(\\nu)$ is sound: any $f$ accepted with probability at least $1/2+\\varepsilon$ is $\\delta(\\varepsilon)$-correlated with some linear character $\\chi_S$. For $k < 1 + 1/\\min\\{p,1-p\\}$, every such test fails: there are functions accepted with constant probability that have vanishing correlation with every linear character. The proof identifies the operative condition as the existence of a pairwise independent coordinate in $\\nu$; the positive direction constructs such distributions with full even-weight support, while the negative direction uses a Gaussian counterexample to show that without one the test cannot be sound. The boundary cases are also settled: $p = 1/(k-1)$ works for all $k\\geqslant 3$, even $k$ at $p = 1 - 1/(k-1)$ works, and odd $k \\geqslant 5$ at $p = 1 - 1/(k-1)$ guarantees correlation with $\\mathbb{Z}/(k-1)\\mathbb{Z}$ characters but not with $\\mathbb{F}_2$-linear functions.","pith_inferences":["The threshold $1+1/\\min\\{p,1-p\\}$ has a simple interpretation as the minimal number of even-parity samples needed before any coordinate can be uncorrelated from the sum of the others; this suggests the same condition may govern other testing problems over biased product measures, such as testing whether a function is a low-degree polynomial.","The odd-$k$ boundary case points toward a hierarchy of characters: the natural test at $p=1-1/(k-1)$ with odd $k$ detects structure modulo $k-1$ rather than modulo 2. A quantitative analysis of how much correlation with $\\mathbb{Z}/(k-1)\\mathbb{Z}$ characters translates into correlation with $\\mathbb{F}_2$-linear characters would be a natural next step.","The proof of the negative half converts a Gaussian counterexample into a Boolean one via the central limit theorem and a rounding step; a similar 'Gaussian-first' route might give counterexamples for other testing problems where the uniform hypercube analogue is already understood.","The theorem is stated for constant $\\varepsilon, \\delta$; extracting explicit bounds on the constants (how large $n$ must be, how small $\\delta$ is relative to $\\varepsilon$) would make the result usable in hardness-of-approximation reductions."],"forward_implications":["For $p=1/2$ the threshold $k>3$ recovers the classical BLR test as the minimal working query count, and shows every 2-query test fails in the 1% regime.","For any fixed finite query budget $k$, the 1% regime is achievable only for $p$ in the interval $[1/(k-1), 1-1/(k-1)]$; outside it, no parity-respecting $k$-query test can be sound.","At the boundary $p = 1/(k-1)$, the tests work for every $k \\geq 3$; this includes the 4-query case at $p=1/3$, recovering the previously known $p\\in(1/3,2/3)$ result as a special case.","The negative construction yields explicit functions, not just existence: they are formed by rounding $h\\big((\\sum_j X_j - np)/\\sqrt{np(1-p)}\\big)$ for a fixed univariate Lipschitz function $h$, so the failure mode below the threshold is concrete.","Because every linear function is accepted with probability 1, these tests are tolerant in the sense that functions close to linear are accepted with high probability; the 1%-regime guarantee is the strong direction."],"supporting_citations":[{"why":"The four-query linearity-testing theorem whose proof (direct product, list decoding, invariance) the paper generalizes to arbitrary $k$ and $p$.","marker":"[BKM23b]"},{"why":"Introduces the 3-query linearity test over the uniform hypercube that serves as the base 'contains BLR' subtest in Theorem 33.","marker":"[BLR93]"},{"why":"Extends the BLR analysis to the 1% regime over the uniform measure, the prototype for the biased 1%-regime question.","marker":"[BCH+96]"},{"why":"Gives an alternative proof of the uniform 1% regime, providing the pattern of constant-advantage-to-constant-correlation that the biased result follows.","marker":"[KLX10]"},{"why":"Constructs the 4-query tolerant $p$-biased test for the 99% regime whose distribution demonstrates that 99%-regime tests can fail in the 1% regime.","marker":"[DFH19]"},{"why":"Invariance principle used in Step 4 to pass from the biased product distribution to Gaussian variables and to enforce pairwise independence.","marker":"[MOO10]"},{"why":"Together with [BKLM24b], supplies the cyclic-character analysis for the corner case of odd $k \\geq 5$ at $p = 1 - 1/(k-1)$.","marker":"[BKLM24a]"},{"why":"Companion work used with [BKLM24a] for the $\\mathbb{Z}/(k-1)\\mathbb{Z}$ character correlation in the boundary case.","marker":"[BKLM24b]"}],"fun_headline_variants":["Tight threshold for biased linearity tests","Pairwise independence sets linearity test threshold","Exact query count found for biased linearity","Threshold for biased linearity tests: k > 1 + 1/p","Pairwise independent coordinate is the key to biased linearity tests"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The positive half of the main theorem depends on a generalization of the four-query linearity-testing theorem to arbitrary $k$ and $p$ that the paper only sketches, importing a direct-product theorem, list-decoding machinery, and an invariance principle from the four-query setting; if any of those imports fails, the existence of tests above the threshold is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Tight threshold for biased linearity tests","Pairwise independence sets linearity test threshold","Exact query count found for biased linearity","Threshold for biased linearity tests: k > 1 + 1/p","Pairwise independent coordinate is the key to biased linearity tests"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000525,"raw_usage":{"total_tokens":2699,"prompt_tokens":1269,"completion_tokens":1430,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":885,"completion_tokens_details":{"reasoning_tokens":1352}},"tokens_in":885,"tokens_out":1430,"duration_ms":10833,"temperature":1.0,"reasoning_tokens":1352,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:04:45.309224+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix $p=0.1$ and $k=10$ (below the threshold $1+1/p = 11$), construct the explicit function from Theorem 24 as $f(x)=h((\\sum_j x_j - np)/\\sqrt{np(1-p)})$ using the Gaussian counterexample from Proposition 19, and numerically verify that for $\\nu \\in D(p,10)$ the acceptance expectation stays above a constant while the maximum correlation with every linear character $\\chi_S$ decays with $n$; if the decay fails, the negative direction of the characterization is wrong.","supporting_citations":[],"review_version":1}