{"id":"59515dbd-b86f-4b59-b09d-cbee881b863e","arxiv_id":"2411.14431","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Near-optimal query bounds for linearity testing under online adversarial corruptions, and an O(1/ε) query tester for real-valued linearity, improving prior O(1/ε log(1/ε)) bounds.","lead":"This paper gives nearly tight answers to two problems about testing whether a function is linear: how well it can be tested when an adversary corrupts answers after each query, and how few queries are needed when the function is defined over the real numbers. It also proves a matching lower bound showing that once the corruption budget gets too large, no test can work at all.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.3's one-sided error guarantee for additivity is not proven: completeness is only argued for linear functions, and the soundness proof invokes Lemma 3.1 in a way that is inconsistent with the claimed one-sided error for non-linear additive functions.","rationale":"The reader correctly identifies the missing completeness proof for non-linear additive functions in Theorem 1.3. My stress-test confirms this and sharpens it: the soundness proof itself is internally inconsistent, invoking Lemma 3.1 in a regime where the lemma is not stated to apply. The proof of Theorem 1.3 uses Lemma 3.1 to assert that if Algorithm 6 accepts with probability at least 1/3, then g is additive and satisfies Pr_x[g(p)=g_x(p)]≥1/2 for all p, but Lemma 3.1 is only stated for inputs passing with probability ≥1/10, which is a different condition and crucially is about the input being close to additive, not far from it. This is not a mere stylistic gap: the claimed one-sided error guarantee for additivity is a central part of Theorem 1.3, and it is not supported by the provided arguments. The online-manipulation results (Theorems 1.1 and 1.2) appear solid and are not in question. The low-degree results inherit the same one-sided-error issue, but the additivity gap is more fundamental because the existence of additive non-linear functions is explicitly acknowledged in the paper. I recommend REJECT over CONDITIONAL because the stated theorem is not merely missing a minor detail; the proof as written supports at most a two-sided or restricted statement. With a corrected completeness argument for additivity, the paper could be acceptable, but as written the central new claim is unproven.","tokens_in":18171,"tokens_out":1627,"duration_ms":16136,"concrete_test":"Re-derive Lemma 3.1 from FY20 for the case where f is an arbitrary additive but non-linear function. Specifically, check whether the self-corrected function g defined in (6)-(7) satisfies g(p)=f(p) for all p. Construct an explicit additive non-linear f on R^n via a Hamel basis and test the self-correction formula: compute g_x(p)=κ_p f(p/κ_p) for a typical x and compare to f(p). If g_x(p)≠f(p) with positive probability, then Algorithm 5 rejects a valid additive input, disproving one-sided error.","verdict_should_be":"REJECT","load_bearing_attack":"The one-sided error claim for additivity in Theorem 1.3 is unsubstantiated. The completeness proof explicitly covers only linear functions: 'if f is linear, Algorithm 6 always accepts, and moreover, (i) g≡f and (ii) for all p,x, g(p)=gx(p), ensuring Algorithm 5 also accepts.' For additive non-linear functions (which exist via Hamel bases), the paper gives no argument that gx(p)=f(p) or that the tester accepts. One-sided error requires acceptance with probability 1 on every valid additive input, so this is a genuine gap, not a stylistic choice. Moreover, the soundness proof is internally inconsistent: it assumes f is ε-far from all additive functions, then invokes Lemma 3.1 to conclude g is additive, but Lemma 3.1 is only stated for functions passing the characterization test with probability at least 1/10, not for functions ε-far from additive. The proof also uses the claim that g is well-defined and corrects f with probability ≥1/2, which is not established in the far-from-additive regime. The paper's statement that the additivity tester 'follows from the same arguments as in [FY20]' does not help, since FY20's tester is for linearity, not additivity. Thus the main new O(1/ε) result for additivity is not proven; the linearity claim may survive, but the additivity claim needs a separate completeness argument or a corrected statement.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies linearity testing in two distinct settings. In the online manipulation model over F2 (Section 2), it presents a query-optimal tester resilient to t online manipulations per query for all t ≤ c·min{ε^2, 1/n^2}·2^n, combining a simplified k-point tester for small t and a sample-based tester for large t, and proves an impossibility result for t ≥ 20ε^2·2^n. In the distribution-free setting over the reals (Section 3), the paper claims O(1/ε)-query testers for additivity and for linearity of continuous functions, improving the Fleming-Yoshida tester, and extends the technique to degree-d polynomial testing with O(d^5 + d^2/ε) queries.","tokens_in":18447,"tokens_out":27476,"duration_ms":224386,"significance":"The online manipulation results are the strongest contribution: Theorem 1.1 gives a doubly optimal tester, and the sample-based tester observation (Theorem 2.6) is clean and useful. The impossibility result is a natural complement. The real-valued results, if correct, would be optimal and would simplify prior work. However, the additivity part of Theorem 1.3 has a serious gap in its one-sided error guarantee, and the linearity part is asserted without a complete proof. The low-degree tester (Theorem 1.4) appears sound and is a nice improvement. Overall, the paper contains significant and correct results in the online model, but the claims for additivity testing over the reals require major revision.","major_comments":[{"comment":"The one-sided error guarantee for additivity is not established and, as stated, is incorrect. The completeness proof covers only linear functions: 'if f is linear, Algorithm 6 always accepts, and moreover, (i) g≡f and (ii) for all p,x∈R^n, g(p)=g_x(p), ensuring Algorithm 5 also accepts f.' Additive non-linear functions exist via Hamel bases. For such f, Eq. (6) gives g_x(p)=κ_p f(p/κ_p). When ||p||_2>1/50, κ_p=50||p||_2 is generally irrational, so f(p/κ_p) need not equal f(p)/κ_p, and hence g_x(p) need not equal f(p). If the unknown distribution D is a point mass at such a p, Algorithm 5 line 5 rejects with probability 1 on a valid additive input. Lemma 3.1 only guarantees that g is additive and that g_x(p) agrees with g(p) with probability >1/2; it does not imply g(p)=f(p). A separate completeness argument for all additive functions, or a change of the theorem statement to two-sided error, is required.","section":"§3.1, Theorem 1.3 (additivity claim)"},{"comment":"The linearity part of Theorem 1.3 is asserted but not proved. The text says 'the tester for linearity follows from the same arguments as in [FY20] where one uses our modified query-g subroutine in both their testers.' The additivity soundness proof relies on the fact that g is additive and f is ε-far from all additive functions, so that Pr_{p∼D}[f(p)≠g(p)]≥ε. For linearity, Lemma 3.1 only guarantees that g is additive, not linear, and f is only assumed ε-far from all linear functions, so the analogous step does not apply. The paper should either provide the precise FY20 argument adapted to the modified subroutine, or state explicitly which additional conditions (e.g., continuity of f) are used and how the constant-accuracy evaluation suffices.","section":"§3.1, Theorem 1.3 (linearity claim)"}],"minor_comments":[{"comment":"The sentence 'we have g_q(c_i p)≠g(c_i p) with probability most 1 − 1/(7d)' should read 'with probability at most 1/(7d)', or equivalently 'g_q(c_i p)=g(c_i p) with probability at least 1−1/(7d)'. The subsequent union bound uses the correct bound.","section":"§3.2, Claim 3.5"},{"comment":"The line 'Accept if span(X)≠{0,1}^n' is confusing, as it appears to accept when the sample does not span the whole space. The accompanying comment 'w.h.p. this doesn't happen' clarifies the intent, but the line should be rephrased and the role of this fallback acceptance should be explained.","section":"§2.2, Algorithm 3"},{"comment":"The surname is misspelled as 'Kalmaj' in the Section 2 heading and in the text; the correct spelling is 'Kalemaj', matching the reference [KRV23].","section":"§2, heading and text"},{"comment":"These theorems are stated with proofs omitted. While they are said to follow from the same arguments as Theorem 1.4, the omission makes them difficult to verify, especially given the gap in Theorem 1.3. Please provide at least proof sketches.","section":"§3.2, Theorems 3.6 and 3.7"}],"recommendation":"major_revision","confidential_remarks":"The gap in Theorem 1.3 is more than a missing proof: for a point-mass distribution D at a vector p with ||p||_2>1/50, the tester can reject a non-linear additive function with probability 1, so the one-sided error claim as stated is false. The authors should either redesign the self-corrector to preserve additivity or weaken the claim to two-sided error. The online manipulation part is solid and is the strongest contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the online-manipulation half is the real contribution: the sample-based tester observation is clean, and the matching impossibility for t >= 20ε^2·2^n rounds out the story nicely. I think that half is correct. Second, the real-valued half has a genuine completeness bug: Theorem 1.3's additivity claim is not proved for all additive functions, and as stated I suspect it is false.\n\nWhat's new and good: Theorem 1.1 covers essentially the full range of t, up to constants; the simplification of the BKMR tester in Case I is sensible and the proof of Lemma 2.4 is careful. The use of Goldreich-Ron sample-based testers to weather an online adversary is an elegant idea, and Theorem 2.6 is a generally useful statement. The impossibility argument via Fischer's lower-bound formalism is coherent and gives the right constant-factor threshold. If I were refereeing, I'd be happy with this part.\n\nThe soft spot: the additivity tester in Section 3.1. The completeness proof explicitly handles only linear f. But the theorem promises additivity, and the authors themselves cite Hamel for non-linear additive functions. For any additive f, the self-correction in (6) simplifies to g_x(p) = κ_p f(p/κ_p). For linear f this equals f(p); for non-linear additive f it does not, except possibly on a measure-zero set, because κ_p is a real scalar, not rational. So the tester can reject a valid additive input with probability close to 1 if the distribution D has mass outside the small ball. That is not a minor gap: it breaks the one-sided error claim and likely the two-sided guarantee as well. The soundness side is fine—the invocation of Lemma 3.1 is legitimate once Algorithm 6 accepts with probability at least 1/3, so the stress-test's inconsistency worry there doesn't land. The problem is purely completeness (and the theorem's statement). The linearity-for-continuous-functions version may survive, and the low-degree results (Theorem 1.4) look okay because the property there is polynomial, not additive pathologies.\n\nBottom line: this paper deserves a serious referee, but the real-valued additivity theorem should be corrected or the paper should restrict Theorem 1.3 to continuous/additive-linear functions. I'd send it to review with that caveat, and I'd cite the online-manipulation results in my own work.","headline":"The online-manipulation half is solid and new; the real-valued additivity theorem has a completeness bug that needs fixing before it is true as stated.","tokens_in":19003,"tokens_out":7017,"would_cite":true,"duration_ms":66813,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper gives optimal linearity testers that tolerate online manipulation for almost the full range of budgets, and cuts real-domain linearity testing to O(1/ε) queries.","keywords":["linearity testing","property testing","online manipulations","sample-based testing","self-correction","distribution-free testing","low-degree testing"],"falsifier":"Take a discontinuous additive $f:\\mathbb{R}\\to\\mathbb{R}$ (a Hamel-basis construction) and let $D$ be a point mass at some $p$ with $f(p)\\neq g(p)$, where $g$ is the self-corrected function of (6)--(7). Run Algorithm 5; since a one-sided tester must accept every valid additive input with probability 1, any rejection -- in particular from Algorithm 6's third test, which can fail for such $f$ -- falsifies the one-sided additivity guarantee in Theorem 1.3.","tokens_in":17944,"feed_emoji":"🔍","tokens_out":14029,"duration_ms":113183,"temperature":0.7,"pith_summary":"Linearity testing asks whether a function is linear or far from every linear function using as few oracle calls as possible. This paper solves two open versions of that question. In the online-manipulation model, where an adversary can erase or corrupt up to $t$ input entries after every query, it constructs an $\\varepsilon$-tester with $O(\\max\\{1/\\varepsilon, \\log t\\})$ queries for all $t$ up to $c\\cdot\\min\\{\\varepsilon^2, 1/n^2\\}\\cdot 2^n$, and proves that no tester exists once $t$ reaches $20\\varepsilon^2 2^n$; the two bounds are tight up to constants. The key move is a regime switch: for small $t$ use a simplified $k$-point test, and for large $t$ switch to sample-based testing, which is automatically robust to manipulation. Over the reals, the paper removes the extra $\\log(1/\\varepsilon)$ factor from distribution-free linearity/additivity testing, giving $O(1/\\varepsilon)$ queries, by observing that each evaluation of the self-corrected function only needs to succeed with constant probability. The same modification improves distribution-free low-degree polynomial testing to $O(d^5 + d^2/\\varepsilon)$ queries for constant degree $d$.","feed_headline":"Optimal linearity testing survives nearly every manipulation budget","feed_subtitle":"A regime switch to sample-based testers closes the online-model gap; real-domain tests fall to O(1/ε) queries.","key_machinery":"The machinery is a pair of regime-shifting primitives plus a self-correction object. $\\mathrm{XorTest}_k$, the $k$-point test, chooses $k$ random points and checks the parity constraint $f(\\oplus_i x_i)=\\prod_i f(x_i)$; its rejection probability is amplified by a factor $\\approx k$ over the 3-point test, which is what makes $O(\\log t + 1/\\varepsilon)$ queries attainable when $t$ is small. Sample-based testing, in the form of the Goldreich--Ron tester, draws $\\Theta(n+1/\\varepsilon)$ uniformly random labeled samples and either extrapolates a linear function from a basis or rejects; because all queries are random and independent of previous answers, the probability that any sample lands on an adversarially manipulated coordinate is at most $q^2 t/2^n$, so the adversary is neutralized for large $t$. Over the reals, the central object is the self-corrected function $g(p)=\\mathrm{maj}_{x\\sim N(0,I)} \\kappa_p (f(p/\\kappa_p - x)+f(x))$, where $\\kappa_p$ radially contracts $p$ into a small ball; a single random direction $x$ gives the 'opinion' $g_x(p)$, and the paper shows one such opinion is enough per test point. The impossibility direction uses Fischer's hard-distribution argument, which concentrates on the $\\ell$ least-queried disagreement points and lets the adversary hide them within the manipulation budget.","core_discovery":"The paper's central claim is a doubly optimal result for linearity over $\\mathbb{F}_2$ in the online-manipulation model: for every budget $t \\le c\\cdot\\min\\{\\varepsilon^2, 1/n^2\\}\\cdot 2^n$ there is an $\\varepsilon$-tester making $O(\\max\\{1/\\varepsilon, \\log t\\})$ queries, and for $t \\ge 20\\varepsilon^2 2^n$ no $\\varepsilon$-tester exists. The upper bound reuses [BKMR24]'s $k$-point test in the small-$t$ regime and switches to Goldreich--Ron sample-based testing in the large-$t$ regime, where the sample complexity $\\Theta(n+1/\\varepsilon)$ coincides with $\\Theta(\\log t + 1/\\varepsilon)$. The impossibility extends Fischer's hard-distribution argument to show that any property with a YES instance and a constant-far NO instance becomes untestable once the adversary can manipulate an $\\varepsilon$-fraction of the input within the tester's first $O(1/\\varepsilon)$ queries. Over the reals, the paper claims a one-sided-error distribution-free $O(1/\\varepsilon)$-query tester for additivity and for linearity of continuous functions, improving Fleming--Yoshida's $O((1/\\varepsilon)\\log(1/\\varepsilon))$; the proof's insight is that a correct evaluation of the self-corrected function $g$ at a single witness point with constant probability is enough, since the other evaluations may be erroneous. The same repair removes the $\\log(1/\\varepsilon)$ factor from the degree-$d$ polynomial testers of [ABF+23].","pith_inferences":["Beyond the paper, the regime-switch principle is likely portable: any property with an optimal sample-based tester and a $k$-point-style combination test should inherit a doubly optimal online tester with the same threshold $t\\approx\\Theta(\\varepsilon^2 N)$.","Beyond the paper, the observation that a constant-probability-correct self-correction suffices suggests that other algorithms amplifying an inner self-corrector to error $1-O(\\varepsilon)$ only for a union bound can drop that amplification, potentially improving related distribution-free tests.","A concrete scope check: if Theorem 1.3 is interpreted literally for additivity, it must accept all Hamel-basis additive functions; testing Algorithm 5 on a discontinuous additive function would settle whether the one-sided guarantee is real or only holds for linear inputs.","The impossibility threshold $t=\\Theta(\\varepsilon^2 N)$ draws a clean line: below it linearity is testable with optimal queries, at it every property with a constant-far NO instance becomes untestable, so the online model offers no intermediate regime for such properties."],"forward_implications":["Linearity over $\\mathbb{F}_2$ is testable with $O(\\log t + 1/\\varepsilon)$ queries against budget-managing online adversaries for every $t \\le c\\cdot\\min\\{\\varepsilon^2,1/n^2\\}\\cdot 2^n$, which is the largest manipulation budget for which testing is possible up to constants.","Any property that has a YES instance and a constant-far NO instance becomes untestable in the online model once $t \\ge (10/\\alpha)\\varepsilon^2 N$, so the impossibility is not special to linearity.","Distribution-free additivity and linearity of continuous functions over $\\mathbb{R}$ admit one-sided-error testers with $O(1/\\varepsilon)$ queries, removing the $\\log(1/\\varepsilon)$ factor from the previous real-domain testers.","The same $O(1/\\varepsilon)$ query bound is obtained for distribution-free testing of degree-$d$ polynomials over the reals for constant $d$, including the approximate and rational-lattice variants."],"supporting_citations":[{"why":"Introduces the online-manipulation model and the k-point test, and proves the $\\Omega(\\log t)$ lower bound that the new tester matches.","marker":"[KRV23]"},{"why":"Gives the previous optimal tester for t up to about $2^{n/2}$ and the soundness lemma showing the k-point test's rejection probability grows with k; the new algorithm simplifies and extends it.","marker":"[BKMR24]"},{"why":"Defines sample-based testing and proves a $\\Theta(n+1/\\varepsilon)$ sample test for linearity, the primitive used in the large-t regime.","marker":"[GR16]"},{"why":"Supplies the hard-distribution lower-bound argument that the impossibility theorem adapts to show properties are untestable when $t \\ge \\Theta(\\varepsilon^2 N)$.","marker":"[Fis24]"},{"why":"Gives the distribution-free self-correction framework and the $O((1/\\varepsilon)\\log(1/\\varepsilon))$ real-domain testers that Theorem 1.3 improves to $O(1/\\varepsilon)$.","marker":"[FY20]"},{"why":"Provides the real-domain degree-d polynomial testers whose $\\log(1/\\varepsilon)$ factor Theorem 1.4 removes.","marker":"[ABF+23]"}],"fun_headline_variants":["Optimal linearity tests handle nearly all tampering budgets","Sample-based testers close the online-manipulation gap","Optimal O(1/ε) tester for real-domain linearity","From online tampering to reals: linearity testing optimized"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the real additivity tester to keep one-sided error, every additive function must agree with its self-corrected version on the checked points; the paper only proves this for linear functions, and additive-but-not-linear functions can violate it.","fun_headline_variants_meta":{"raw":{"variants":["Optimal linearity tests handle nearly all tampering budgets","Sample-based testers close the online-manipulation gap","Optimal O(1/ε) tester for real-domain linearity","From online tampering to reals: linearity testing optimized"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000959,"raw_usage":{"total_tokens":4250,"prompt_tokens":1274,"completion_tokens":2976,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":890,"completion_tokens_details":{"reasoning_tokens":2905}},"tokens_in":890,"tokens_out":2976,"duration_ms":20513,"temperature":1.0,"reasoning_tokens":2905,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:13:19.155878+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a discontinuous additive $f:\\mathbb{R}\\to\\mathbb{R}$ (a Hamel-basis construction) and let $D$ be a point mass at some $p$ with $f(p)\\neq g(p)$, where $g$ is the self-corrected function of (6)--(7). Run Algorithm 5; since a one-sided tester must accept every valid additive input with probability 1, any rejection -- in particular from Algorithm 6's third test, which can fail for such $f$ -- falsifies the one-sided additivity guarantee in Theorem 1.3.","supporting_citations":[],"review_version":1}