{"id":"4044ea1d-b166-4de4-a075-8a3c600e2c26","arxiv_id":"2411.18617","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Online (adaptive) adversarial manipulation of inputs is incomparable to offline (pre-committed) manipulation in query complexity, and can require exponentially more random bits.","lead":"Property testing checks whether huge data satisfies a simple property by reading only a few random entries. This paper shows that whether damage to the data is chosen before or during the check changes both the number of reads and the randomness needed, and the two settings are incomparable.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 4.2 overclaims one-sided random-bit lower bound: Ω(√n/log n) follows, not Ω(√n); the exponential separation still stands.","rationale":"The paper's central contributions are the query-complexity incomparability (Theorem 3.1 and Corollaries 3.2-3.3) and the exponential randomness separation (Theorem 4.1 and Corollary 4.2's two-sided bound). I verified the main reductions: Lemma 3.5's lifting argument is technically sound, and Lemma 4.3's randomness-to-queries reduction is valid because the adversary can simulate all random seeds and each non-erased query reduces the consistent seed set by a factor of t+1. Lemma 4.6's query lower bound correctly leverages the Goldreich-Ron sample-based tester conversion (Fact 4.7), which is a standard theorem for symmetric properties; the VV10 sample lower bound transfers to strings via empirical distributions that are O(m/n)-close in total variation, which is achievable by count rounding. The reader's flagged concern about Fact 4.7 is therefore not a real weakness. However, the one-sided lower bound in Corollary 4.2 is overstated: with τ = Θ(√n/log n), the theorem gives Ω(√n/log n), not Ω(√n). This is a genuine but local error that does not undermine the main exponential separation. The conditional verdict remains appropriate pending a correction or justification of that one-sided claim.","tokens_in":17702,"tokens_out":29202,"duration_ms":253056,"concrete_test":"Recompute the one-sided lower bound by substituting τ = 0.01ε√n/log n and t=1 into Theorem 4.1 Item 3: the resulting bound is Ω(τ log(t+1)) = Ω(√n/log n). Check whether any part of Section 4.2 or Lemma 4.6 supplies an improved one-sided query lower bound of Ω(√n) for this τ; absent such an argument, the Ω(√n) claim in Corollary 4.2 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The core randomness separation (Theorem 4.1) is sound; the reader's concern about Fact 4.7 does not land because the Goldreich–Ron conversion of symmetric-property testers to sample-based testers with O(q) samples is a known theorem and applies here. The real issue is Corollary 4.2's final sentence: with τ = Θ(√n/log n) and t=1, Theorem 4.1 Item 3 gives a one-sided lower bound of Ω(τ log(t+1)) = Ω(√n/log n) random bits, not Ω(√n). The two-sided bound Ω(√n/polylog n) is valid, so the claimed exponential separation between O(log n) offline random bits and any online tester is unaffected. The overclaim is confined to the stated corollary and should be weakened or justified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper compares property testing under offline and online adversarial manipulation of the input. The first set of results (Theorem 3.1 and Corollaries 3.2--3.3) shows that the offline-erasure and online-corruption models are incomparable in query complexity: a repetition-code lifting construction makes properties that are trivial for an online-corruption tester but require nearly linear queries for an offline-erasure tester. The second set of results (Theorem 4.1 and Corollary 4.2) shows an exponential separation in randomness complexity: there is a property testable with O(sqrt(n)/log n) queries against both online and offline adversaries, where the offline tester uses O(log n) random bits but every online-erasure tester requires sqrt(n)/polylog n random bits. The main technical tools are a lifting lemma for repetition codes (Lemma 3.5), a reduction from randomness-efficient online testers to query-efficient standard testers (Lemma 4.3), and a query lower bound for tau-Distinct-Elements based on VV10 hard instances (Lemma 4.6).","tokens_in":17821,"tokens_out":21318,"duration_ms":202473,"significance":"If the results are correct, the paper closes a natural open question from Kalemaj et al. and establishes that online and offline adversarial models are genuinely incomparable, both in query complexity and in randomness complexity. The lifting lemma and the random-seed elimination reduction are clean and potentially reusable ideas. The proofs of the main theorems are detailed and internally consistent: the repetition-test analysis (Claim 3.7), the E1/E2 union bound (Claim 3.8), the corrupted-query bound in Lemma 3.5, the seed elimination argument in Lemma 4.3, and the use of VV10 hard instances in Lemma 4.6 all check out. I also examined the potential concern about Fact 4.7: the Goldreich--Ron conversion from query testers to sample-based testers for symmetric properties is a known theorem and its use here is legitimate, so the dependency is not circular. One statement in Corollary 4.2 overclaims a one-sided random-bit bound by a logarithmic factor; the corrected bound still preserves the exponential separation, and the rest of the core results remain valid.","major_comments":[{"comment":"The final sentence of Corollary 4.2 overclaims the one-sided random-bit lower bound. With tau = 0.01*epsilon*sqrt(n)/log n and t = 1, Theorem 4.1, Item 3 gives Omega(tau*log(t+1)) = Omega(sqrt(n)/log n) random bits for one-sided testers, not Omega(sqrt(n)). The proof as written supports only the weaker bound, and the stronger bound would require a separate argument, for example a one-sided query lower bound of Omega(tau) for tau as large as sqrt(n), which is not supplied. The two-sided bound Omega(sqrt(n)/polylog n) remains valid, so the claimed exponential separation between O(log n) offline random bits and any online tester is unaffected, but the corollary's final sentence is false as stated and should be weakened to Omega(sqrt(n)/log n) or justified by a new proof.","section":"§4, Corollary 4.2 (and Theorem 4.1, Item 3)"}],"minor_comments":[{"comment":"The phrase \"the second (Theorem 1.1)\" should refer to Theorem 1.3, not Theorem 1.1.","section":"§1, paragraph after Theorem 1.1"},{"comment":"The phrase \"tempered with\" should read \"tampered with.\"","section":"Definition 2.6"},{"comment":"The proof cites Fact 4.7 as a black-box conversion from query testers to sample-based testers; since this is the step that turns the VV10 sample bound into a query bound, a sentence stating the precise formulation and the dependence of the O(q) sample complexity on the error probability would improve self-containedness.","section":"§4.1, Lemma 4.6"},{"comment":"The first sentence's phrase \"for every constant epsilon\" is slightly imprecise: the upper-bound part of the corollary holds for all epsilon in (0,1), while the lower-bound part only supplies one constant epsilon; this distinction should be made explicit.","section":"§4, Corollary 4.2"}],"recommendation":"major_revision","confidential_remarks":"The technical core of the paper is sound and the results are significant. The only substantive issue I found is the one-sided random-bit overclaim in Corollary 4.2; it is local and can be fixed by weakening the bound to Omega(sqrt(n)/log n). The paper fits the journal's scope and should be publishable after this correction."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is the short version: the paper's main theorems are sound, and the exponential randomness separation is real. The one thing to fix is a log-factor overclaim in Corollary 4.2.\n\nThe paper answers the open question from KRV23: online and offline erasure/corruption models are incomparable in query complexity. The repetition-code lifting lemma is a clean, useful way to push BFLR20's offline-vs-standard separation into the online setting. The randomness lower bound in Theorem 4.1 uses a neat reduction (Lemma 4.3): a tester with r random bits against a t-online-erasure adversary implies a standard tester with r/log(t+1) queries, via a consistent-seed adversary that erases the most likely next queries. That reduction is the real contribution, and it checks out. The VV10-based query lower bound for tau-Distinct-Elements is carefully adapted; the reader's concern that Fact 4.7 (Goldreich-Ron) might fail in this regime does not land, since that conversion is a known theorem for symmetric properties and the property is symmetric.\n\nSoft spot: Corollary 4.2's final sentence says a one-sided-error 1-online-erasure tester requires Omega(sqrt(n)) random bits. From Theorem 4.1 Item 3, with tau = Theta(sqrt(n)/log n) and t = 1, the one-sided bound is Omega(tau log(t+1)) = Omega(sqrt(n)/log n), not Omega(sqrt(n)). The theorem's condition tau <= 0.01 sqrt(n)/log n prevents choosing tau to close the gap. So the corollary's last sentence is not supported as stated. This is a minor quantitative overclaim: the two-sided Omega(sqrt(n)/polylog n) lower bound is valid and still gives the exponential separation over the O(log n) offline randomness. The authors should weaken or justify that sentence.\n\nThe rest of the analysis is solid. The lifting lemma's union bound is loose but sufficient. Citation practice looks appropriate: self-citations are context and prior testers, not load-bearing; the reduction to VV10 is explicit and not circular.\n\nWho gets value: anyone working on property testing with adversarial noise, and people interested in derandomization lower bounds. It deserves a serious referee. My recommendation: send it to peer review; accept after a minor revision that fixes Corollary 4.2's one-sided bound.","headline":"Solid paper answering KRV23's open question; the exponential randomness separation holds, but Corollary 4.2 overclaims the one-sided bound by a log factor.","tokens_in":18384,"tokens_out":3456,"would_cite":true,"duration_ms":30955,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The online and offline adversarial models of property testing are incomparable: some properties are easier online, while others force exponentially more randomness online.","keywords":["property testing","online adversary","offline erasure","query complexity","randomness complexity","tau-Distinct-Elements","repetition code","support size approximation"],"falsifier":"Exhibit a one-online-erasure-resilient tester for $\\tau$-Distinct-Elements with $\\tau = \\sqrt{n}/\\log n$ that uses $o(\\sqrt{n}/\\operatorname{polylog} n)$ random bits, or demonstrate a symmetric property with a superlinear gap between query complexity and sample-based sample complexity in that parameter range; either would break Theorem 4.1.","tokens_in":17457,"feed_emoji":"🎲","tokens_out":5540,"duration_ms":48217,"temperature":0.7,"pith_summary":"An adversary who may erase or corrupt symbols while a property tester is still querying the input is usually thought to be strictly more powerful than one who must finish all tampering in advance. This paper shows the two models are incomparable: some properties are easy against an online adversary but hard against an offline one, and vice versa. It constructs properties testable with a constant number of queries under online corruptions that require nearly linear queries under offline erasures, answering an open question of Kalemaj, Raskhodnikova, and Varma. It also constructs a property testable with roughly $\\sqrt{n}/\\log n$ queries in both models whose offline tester uses only $O(\\log n)$ random bits while every online tester needs $\\Omega(\\sqrt{n}/\\operatorname{polylog} n)$ random bits. The query-complexity results rest on a repetition-code lifting lemma, and the randomness result on a reduction from randomness-efficient online testers to query-efficient standard testers.","feed_headline":"Online erasures force exponentially more random bits","feed_subtitle":"The same property needs only O(log n) random bits offline but Omega(sqrt(n)/polylog n) against an online adversary.","key_machinery":"The two load-bearing mechanisms are a lifting lemma and a reduction. The lifting lemma takes any property $P$ testable in the standard model and encodes it as $P^r$ by concatenating $r$ copies of every string; the paper proves this repetition code is robust against online corruptions, so any standard tester lifts to a $t$-online-corruption tester with comparable query complexity. The reduction (Lemma 4.3) converts any $t$-online-erasure-resilient tester using $r$ random bits into a standard-model tester using $r/\\log(t+1)$ queries, through a 'seed-elimination adversary' that erases the indices most likely to be queried under the remaining consistent random seeds. Combining the reduction with a sampling lower bound for the symmetric property $\\tau$-Distinct-Elements yields the exponential randomness gap.","core_discovery":"On the paper's own terms, the central discovery is that the online and offline adversarial models of property testing are not ordered by difficulty. The paper proves query-complexity incomparability via a property that constant-query online testers handle even under corruptions, yet any offline-erasure tester needs $\\widetilde{\\Omega}(n)$ queries. It then proves a randomness separation using the property $\\tau$-Distinct-Elements, the set of strings with at most $\\tau$ distinct symbols: for $\\tau = \\Theta(\\sqrt{n}/\\log n)$, the same simple sampling tester works in both models with $O(\\sqrt{n}/\\log n)$ queries, but the offline tester runs on $O(\\log n)$ random bits while every online tester, even with one erasure per query, must use $\\Omega(\\sqrt{n}/\\operatorname{polylog} n)$ bits. The randomness lower bound is the paper's main technical novelty: any tester that uses $r$ random bits against a $t$-online-erasure adversary yields a standard-model tester with at most $r/\\log(t+1)$ queries, so known query lower bounds become randomness lower bounds.","pith_inferences":["The seed-elimination adversary suggests a broad trade-off: in the online model, randomness is a resource the adversary can deterministically eliminate, so any online tester's randomness cost is at least a logarithmic factor times the query lower bound of the underlying standard problem; this may extend to promise problems beyond property testing.","The lifting lemma applies over any alphabet and to any standardly testable property, so it could produce online-robust versions of monotonicity, linearity, and other testable properties, offering a general toolbox for online testing.","Because the randomness separation holds for constant proximity parameter $\\varepsilon$, it shows that the $O(\\log n)$ derandomization ceiling is tight for online testers in a strong sense; one could try to tighten the constants or extend the statement to two-sided-error testers.","A natural next step would be to transfer these reductions to distribution-testing models, where support-size estimation is already the canonical problem; the techniques may yield analogous online-versus-offline separations for sampling access."],"forward_implications":["The offline and online erasure models are incomparable for query complexity: neither dominates the other, settling the open question raised by Kalemaj, Raskhodnikova, and Varma.","Derandomization in the style of Goldreich and Sheffet cannot extend to online testers: there are properties whose online testers require super-logarithmic randomness for constant proximity.","Any property with a known standard-versus-offline query gap can be lifted via repetition codes to a gap between online and offline testers, so further separations follow from known hard properties.","For symmetric properties, query lower bounds in the standard model translate directly into randomness lower bounds for online testers, giving a general recipe for randomness separations.","The $\\tau$-Distinct-Elements property is testable in both models with the same simple sampling strategy, making it a natural concrete witness for the randomness gap."],"supporting_citations":[{"why":"Defines the online-erasure and online-corruption models and raises the open question of whether offline erasures can ever be harder than online erasures; this paper answers it in the affirmative.","marker":"[KRV23]"},{"why":"Supplies the hard property separating standard testing from offline-erasure-resilient testing, which the lifting lemma turns into a separation between online and offline testers.","marker":"[BFLR20]"},{"why":"Provides the support-size estimation lower bound that becomes the query lower bound for $\\tau$-Distinct-Elements after converting testers to sample-based testers.","marker":"[VV10]"},{"why":"Fact 4.7, stating that symmetric properties have sample-based testers with only linear query blow-up, is the bridge that turns the sampling lower bound into a query lower bound in the standard model.","marker":"[GR15]"},{"why":"Shows all standard model testers can be derandomized to $O(\\log n)$ random bits, which supplies the offline randomness upper bound and frames the quest for an online counterexample.","marker":"[GS10]"},{"why":"Gives the simple sampling tester for $\\tau$-Distinct-Elements that is shown to be resilient against both online and offline erasures.","marker":"[GR22]"},{"why":"Introduces the offline-erasure-resilient testing model whose query-complexity behavior the new results compare against and separate from the online models.","marker":"[DRTV18]"}],"fun_headline_variants":["Online adversary forces exponentially more random bits","Property testing randomness gap: online needs far more","Online vs offline testers: query complexity incomparable","Constant-query online tester beats offline erasure tester","Exponential randomness separation in property testing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every tester for a symmetric property can be converted to a sample-based tester with only a linear blow-up in queries, since this conversion turns the support-size sampling lower bound into the query lower bound that powers the randomness separation.","fun_headline_variants_meta":{"raw":{"variants":["Online adversary forces exponentially more random bits","Property testing randomness gap: online needs far more","Online vs offline testers: query complexity incomparable","Constant-query online tester beats offline erasure tester","Exponential randomness separation in property testing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1517,"prompt_tokens":1021,"completion_tokens":496,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":427}},"tokens_in":637,"tokens_out":496,"duration_ms":5367,"temperature":1.0,"reasoning_tokens":427,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T11:03:45.368877+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a one-online-erasure-resilient tester for $\\tau$-Distinct-Elements with $\\tau = \\sqrt{n}/\\log n$ that uses $o(\\sqrt{n}/\\operatorname{polylog} n)$ random bits, or demonstrate a symmetric property with a superlinear gap between query complexity and sample-based sample complexity in that parameter range; either would break Theorem 4.1.","supporting_citations":[],"review_version":1}