REVIEW 4 major objections 5 minor 29 references
Biased Linearity Testing in the 1% Regime
T0 review · 4 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash
Pith's one-line read Biased linearity tests succeed past a sharp query threshold.
desk verdict 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. 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 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).
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (4)
- [Section 7, Step 4] 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 7, Steps 2–3] 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 6.1, Theorem 31] 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.
- [Lemma 28] 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.
minor comments (5)
- [Abstract and Theorem 5] 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 7, Step 1] 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.
- [Definition 32] 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.
- [Theorem 5, item 3 case (a)] 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 7, Step 2] 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.
Circularity Check
No substantive circularity; the positive half is delegated to overlapping-author prior work and a proof outline, but no claim reduces to its own input by construction.
full rationale
The paper's derivation chain is not circular. The negative direction (Theorem 24) is proved from scratch using a Gaussian construction and rounding, and the query-bias tradeoff in Propositions 25 and 27 is self-contained. The positive direction routes through Theorem 33, whose Section 7 proof is explicitly a rough outline that imports Theorem 1.1 of BKM23b and the BKM23b list-decoding and invariance arguments; this is a heavy dependency on prior work by overlapping authors, but it is a dependency, not a reduction by construction. Similarly, Theorem 31 in Section 6.1 says 'The result follows from the work of Bhangale, Khot, Liu and Minzer [BKLM24a, BKLM24b], and we omit the details', which is an omitted proof and a verification burden, but again not a circular step. No equation in the paper is shown to be its own input by definition, and the cited prior results do not include the present theorem. The self-citations are load-bearing and the positive half is not fully self-contained, so the score is above zero, but the central claim still has independent content and the paper is not circular.
Assumptions & free parameters
assumptions (8)
- standard math Multivariate Central Limit Theorem (Theorem 15) applied to sums of i.i.d. draws from ν and µ_p.
- standard math Hoeffding's inequality (Fact 14) and Chebyshev's inequality (Fact 13).
- standard math Hermite polynomial moment formula (Lemma 18) for Gaussian expectations.
- domain assumption Theorem 1.1 of Bhangale-Khot-Minzer [BKM23b], a direct product test over the biased hypercube.
- domain assumption List-decoding and invariance principle steps from BKM23b (their Sections 4.2-4.6) extend to arbitrary k and to distributions with one pairwise independent coordinate.
- domain assumption Gaussian invariance principles of [MOO10, Mos10, Mos20] apply to low-influence, low-degree functions on the p-biased hypercube.
- domain assumption The characters over Z/(k-1)Z analysis of [BKLM24a, BKLM24b] (Theorem 31) is correct as claimed.
- ad hoc to paper The q-vector formulas in Lemma 28 define a valid probability distribution with the required support, marginal, and pairwise independence properties.
Cite this review
Pith. "Pith review of Biased Linearity Testing in the 1% Regime." pith.science (2026). https://pith.science/paper/KMOSFSV5
@misc{pith2026250201900,
author = {Pith},
title = {Pith review of: Biased Linearity Testing in the 1% Regime},
year = {2026},
howpublished = {\url{https://pith.science/paper/KMOSFSV5}},
note = {Machine review of arXiv:2502.01900}
}
abstract
We study linearity testing over the $p$-biased hypercube $(\{0,1\}^n, \mu_p^{\otimes n})$ in the 1% regime. For a distribution $\nu$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \text{ (mod 2)} \}$, with marginal distribution $\mu_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(\nu)$ proceeds as follows: Given query access to a function $f:\{0,1\}^n\to \{-1,1\}$, sample $(x_1,\dots,x_k)\sim \nu^{\otimes n}$, query $f$ on $x_1,\dots,x_k$, and accept if and only if $\prod_{i\in [k]}f(x_i)=1$. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for $0 < p \leq \frac{1}{2}$, that if $k \geq 1 + \frac{1}{p}$, then there exists a distribution $\nu$ such that the test $\text{Lin}(\nu)$ works in the 1% regime; that is, any function $f:\{0,1\}^n\to \{-1,1\}$ passing the test $\text{Lin}(\nu)$ with probability $\geq \frac{1}{2}+\epsilon$, for some constant $\epsilon > 0$, satisfies $\Pr_{x\sim \mu_p^{\otimes n}}[f(x)=g(x)] \geq \frac{1}{2}+\delta$, for some linear function $g$, and a constant $\delta = \delta(\epsilon)>0$. Conversely, we show that if $k < 1+\frac{1}{p}$, then no such test $\text{Lin}(\nu)$ works in the 1% regime. Our key observation is that the linearity test $\text{Lin}(\nu)$ works if and only if the distribution $\nu$ satisfies a certain pairwise independence property.
Reference graph
Works this paper leans on
-
[1]
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing R eed- M uller codes. IEEE Trans. Inform. Theory , 51(11):4032--4039, 2005
work page 2005
-
[2]
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM , 45(3):501--555, 1998
1998
-
[3]
Probabilistic checking of proofs: a new characterization of NP
Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP . J. ACM , 45(1):70--122, 1998
work page 1998
-
[4]
Linearity testing in characteristic two
Mihir Bellare, Don Coppersmith, Johan H stad, Marcos Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Trans. Inform. Theory , 42(6, part 1):1781--1795, 1996. (also in SFCS 1995)
work page 1996
-
[5]
On Approximability of Satisfiable $k$-CSPs: VI
Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor Minzer. On approximability of satisfiable k- CSP s: VI . 2024. Available at https://arxiv.org/pdf/2411.15133
work page Pith review arXiv 2024
-
[6]
On Approximability of Satisfiable $k$-CSPs: VII
Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor Minzer. On approximability of satisfiable k- CSP s: VII . 2024. Available at https://arxiv.org/pdf/2411.15136
work page Pith review arXiv 2024
-
[7]
On approximability of satisfiable k - CSP s: I
Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k - CSP s: I . In STOC , pages 976--988, 2022
work page 2022
-
[8]
On approximability of satisfiable k- CSP s: II
Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k- CSP s: II . In STOC , pages 632--642, 2023
work page 2023
Show all 29 references
-
[9]
On approximability of satisfiable k- CSP s: III
Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k- CSP s: III . In STOC , pages 643--655, 2023
2023
-
[10]
On approximability of satisfiable k- CSP s: IV
Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k- CSP s: IV . In STOC , pages 1423--1434, 2024
2024
-
[11]
On approximability of satisfiable k- CSP s: V
Amey Bhangale, Subhash Khot, and Dor Minzer. On approximability of satisfiable k- CSP s: V . Electron. Colloquium Comput. Complex. , TR24-129 , 2024
2024
-
[12]
Optimal testing of R eed- M uller codes
Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of R eed- M uller codes. In FOCS , pages 488--497, 2010
2010
-
[13]
Self-testing/correcting with applications to numerical problems
Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. System Sci. , 47(3):549--595, 1993. (also in STOC 1990)
1993
-
[14]
Non-abelian homomorphism testing, and distributions close to their self-convolutions
Michael Ben-or, Don Coppersmith, Mike Luby, and Ronitt Rubinfeld. Non-abelian homomorphism testing, and distributions close to their self-convolutions. Random Structures Algorithms , 32(1):49--70, 2008. (also in APPROX-RANDOM 2004)
2008
-
[15]
Randomness-efficient low degree tests and short PCP s via epsilon-biased sets
Eli Ben-Sasson, Madhu Sudan, Salil Vadhan, and Avi Wigderson. Randomness-efficient low degree tests and short PCP s via epsilon-biased sets. In STOC , pages 612--621, 2003
2003
-
[16]
Direct sum testing
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar. Direct sum testing. SIAM J. Comput. , 46(4):1336--1369, 2017. (also in ITCS 2015)
2017
-
[17]
Analyzing B oolean functions on the biased hypercube via higher-dimensional agreement tests
Irit Dinur, Yuval Filmus, and Prahladh Harsha. Analyzing B oolean functions on the biased hypercube via higher-dimensional agreement tests. In SODA , pages 2124--2133, 2019
2019
-
[18]
Probability---theory and examples
Rick Durrett. Probability---theory and examples . Cambridge University Press, Cambridge, 2019. Fifth edition
2019
-
[19]
Interactive proofs and the hardness of approximating cliques
Uriel Feige, Shafi Goldwasser, Laszlo Lov\' a sz, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. J. ACM , 43(2):268--292, 1996
1996
-
[20]
Distribution-free property-testing
Shirley Halevy and Eyal Kushilevitz. Distribution-free property-testing. SIAM J. Comput. , 37(4):1107--1138, 2007. (also in APPROX-RANDOM 2003, 2005)
2007
-
[21]
Probability inequalities for sums of bounded random variables
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. , 58:13--30, 1963
1963
-
[22]
Breaking the -soundness bound of the linearity test over GF(2)
Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the -soundness bound of the linearity test over GF(2) . SIAM J. Comput. , 39(5):1988--2003, 2010. (also in APPROX-RANDOM 2008)
1988
-
[23]
A dense model theorem for the boolean slice
Gil Kalai, Noam Lifshitz, Tamar Ziegler, and Dor Minzer. A dense model theorem for the boolean slice. In FOCS , 2024. (to appear)
2024
-
[24]
Tolerant linearity testing and locally testable codes
Swastik Kopparty and Shubhangi Saraf. Tolerant linearity testing and locally testable codes. In APPROX-RANDOM , pages 601--614. 2009
2009
-
[25]
Noise stability of functions with low influences: invariance and optimality
Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Ann. of Math. (2) , 171(1):295--341, 2010
2010
-
[26]
Gaussian bounds for noise correlation of functions
Elchanan Mossel. Gaussian bounds for noise correlation of functions. Geom. Funct. Anal. , 19(6):1713--1756, 2010
2010
-
[27]
Gaussian bounds for noise correlation of resilient functions
Elchanan Mossel. Gaussian bounds for noise correlation of resilient functions. Israel J. Math. , 235(1):111--137, 2020
2020
-
[28]
Analysis of B oolean functions
Ryan O'Donnell. Analysis of B oolean functions . Cambridge University Press, New York, 2014
2014
-
[29]
Derandomizing homomorphism testing in general groups
Amir Shpilka and Avi Wigderson. Derandomizing homomorphism testing in general groups. SIAM J. Comput. , 36(4):1215--1230, 2006. (also in STOC 2004)
2006
Reviewed August 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.