REVIEW 1 major objections 4 minor 32 references
Online versus Offline Adversaries in Property Testing
T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The online and offline adversarial models of property testing are incomparable: some properties are easier online, while others force exponentially more randomness online.
desk verdict 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. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (1)
- [§4, Corollary 4.2 (and Theorem 4.1, Item 3)] 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.
minor comments (4)
- [§1, paragraph after Theorem 1.1] The phrase "the second (Theorem 1.1)" should refer to Theorem 1.3, not Theorem 1.1.
- [Definition 2.6] The phrase "tempered with" should read "tampered with."
- [§4.1, Lemma 4.6] 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.
- [§4, Corollary 4.2] 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.
Circularity Check
No circularity: central results are proved by direct reductions and external known theorems; only a minor arithmetic overclaim in Corollary 4.2 is noted.
full rationale
The paper's derivation chain is self-contained against external theorems and does not assume its conclusions. The query-complexity separation (Theorem 3.1 and Corollaries 3.2-3.3) is proved by a directly verified lifting lemma (Lemma 3.5, Claims 3.7-3.8) applied to the external BFLR20 separation (Theorem 3.6); no conclusion of the present paper is used in the proof of the lifting lemma. The randomness separation (Theorem 4.1) combines three independent ingredients: (i) Lemma 4.3, whose proof gives an explicit adversary that eliminates random seeds and converts any r-bit online tester into a standard tester with r/log(t+1) queries; (ii) Lemma 4.6, whose lower bound for tau-Distinct-Elements is derived from the external Goldreich-Ron symmetric-property conversion (Fact 4.7) and the VV10 sample lower bound (Fact 4.8); and (iii) Facts 4.5 and 4.9 for the upper bounds. Fact 4.7 is cited rather than proved, but it is an external theorem from Goldreich and Ron, not a self-citation and not an assumed consequence of this paper's claims. Self-citations such as KRV23 and BKMR24 are used only to define the online model and to cite existing testers or context; they are not load-bearing. No fitted parameter is relabeled as a prediction, and no uniqueness claim is imported from the authors' prior work. The only issue noticed is a minor arithmetic overstatement in Corollary 4.2, where Theorem 4.1 Item 3 with tau = Theta(sqrt(n)/log n) and t = 1 yields Omega(sqrt(n)/log n) one-sided random bits rather than Omega(sqrt(n)); this is a correctness slip, not a circularity, and it does not affect the claimed exponential separation. Overall the proof chain is not circular.
Assumptions & free parameters
assumptions (6)
- standard math Standard probability tools: Markov, Chernoff, union bound.
- domain assumption Online adversary model (Definition 2.6): adversary knows the algorithm and query history but not future coin tosses.
- domain assumption BFLR20 Theorem 6.2: existence of Q^(ell) with standard query complexity (2/epsilon)^{O(ell)} and offline-erasure lower bound Omega(m/(10 ell polylog^ell m)).
- domain assumption VV10 support-size lower bound (Fact 4.8): distinguishing hard distributions needs Omega(m/log m) samples.
- domain assumption GR15 Fact 4.7: symmetric properties have sample-based testers with O(q) samples.
- domain assumption GS10/Gol17 Fact 4.9: any q-query randomized oracle machine can be simulated with log n + log log |Sigma| + O(1) random bits.
Cite this review
Pith. "Pith review of Online versus Offline Adversaries in Property Testing." pith.science (2026). https://pith.science/paper/WIJEY7T3
@misc{pith2026241118617,
author = {Pith},
title = {Pith review of: Online versus Offline Adversaries in Property Testing},
year = {2026},
howpublished = {\url{https://pith.science/paper/WIJEY7T3}},
note = {Machine review of arXiv:2411.18617}
}
read the original abstract
We study property testing with incomplete or noisy inputs. The models we consider allow for adversarial manipulation of the input, but differ in whether the manipulation can be done only offline, i.e., before the execution of the algorithm, or online, i.e., as the algorithm runs. The manipulations by an adversary can come in the form of erasures or corruptions. We compare the query complexity and the randomness complexity of property testing in the offline and online models. Kalemaj, Raskhodnikova, and Varma (Theory Comput `23) provide properties that can be tested with a small number of queries with offline erasures, but cannot be tested at all with online erasures. We demonstrate that the two models are incomparable in terms of query complexity: we construct properties that can be tested with a constant number of queries in the online corruption model, but require querying a significant fraction of the input in the offline erasure model. We also construct properties that exhibit a strong separation between the randomness complexity of testing in the presence of offline and online adversaries: testing these properties in the online model requires exponentially more random bits than in the offline model, even when they are tested with nearly the same number of queries in both models. Our randomness separation relies on a novel reduction from randomness-efficient testers in the adversarial online model to query-efficient testers in the standard model.
Reference graph
Works this paper leans on
-
[1]
Refining the adaptivity notion in the huge object model
Tomer Adar and Eldar Fischer. Refining the adaptivity notion in the huge object model. In Amit Kumar and Noga Ron - Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK , volume 317 of LIPIcs , pages 45:1--45:16. Schloss Dagstu...
work page 2024
-
[2]
Support testing in the huge object model
Tomer Adar, Eldar Fischer, and Amit Levi. Support testing in the huge object model. In Amit Kumar and Noga Ron - Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, August 28-30, 2024, London School of Economics, London, UK , volume 317 of LIPIcs , pages 46:1--46:16. Schloss Dagstuhl ...
work page 2024
-
[3]
On optimal testing of linearity
Vipul Arora, Esty Kelman, and Uri Meir. On optimal testing of linearity. In Symposium on Simplicity in Algorithms (SOSA) . SIAM, 2025. To appear
work page 2025
-
[4]
Adaptive lower bound for testing monotonicity on the line
Aleksandrs Belovs. Adaptive lower bound for testing monotonicity on the line. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages 31:1--31:10, 2018
work page 2018
- [5]
- [6]
-
[7]
Property testing with online adversaries
Omri Ben-Eliezer , Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property testing with online adversaries. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA , volume 287 of LIPIcs , pages 11:1--11:25. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Infor...
work page 2024
- [8]
Show all 32 references
-
[9]
Improved testing algorithms for monotonicity
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky. Improved testing algorithms for monotonicity. In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages 9...
1999
-
[10]
Erasure-resilient property testing
Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma. Erasure-resilient property testing. SIAM Journal on Computing (SICOMP) , 47(2):295--329, 2018
2018
-
[11]
Spot-checkers
Funda Erg \"u n, Sampath Kannan, Ravi Kumar, Ronitt Rubinfeld, and Mahesh Viswanathan. Spot-checkers. J. Comput. Syst. Sci. , 60(3):717--751, 2000
2000
-
[12]
Tolerant versus intolerant testing for boolean properties
Eldar Fischer and Lance Fortnow. Tolerant versus intolerant testing for boolean properties. Theory Comput. , 2(9):173--183, 2006
2006
-
[13]
and Nathaniel Harms
Renato Ferreira Pinto Jr. and Nathaniel Harms. Testing support size more efficiently than learning histograms. 2024
2024
-
[14]
On the strength of comparisons in property testing
Eldar Fischer. On the strength of comparisons in property testing. Inf. Comput. , 189(1):107--116, 2004
2004
-
[15]
Property testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. Journal of the ACM , 45(4):653--750, 1998
1998
-
[16]
Introduction to property testing
Oded Goldreich. Introduction to property testing . Cambridge University Press, 2017
2017
-
[17]
On sample-based testers
Oded Goldreich and Dana Ron. On sample-based testers. In Tim Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015 , pages 337--345. ACM , 2015
2015
-
[18]
Testing distributions of huge objects
Oded Goldreich and Dana Ron. Testing distributions of huge objects. CoRR , abs/2212.12802, 2022
2022 arXiv
-
[19]
On the randomness complexity of property testing
Oded Goldreich and Or Sheffet. On the randomness complexity of property testing. Computational Complexity , 19:99--133, 2010
2010
-
[20]
Testing and reconstruction of Lipschitz functions with applications to data privacy
Madhav Jha and Sofya Raskhodnikova. Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM Journal on Computing (SICOMP) , 42(2):700--731, 2013
2013
-
[21]
Sublinear-time computation in the presence of online erasures
Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma. Sublinear-time computation in the presence of online erasures. Theory Comput. , 19 (1):1--48, 2023
2023
-
[22]
Pallavoor, Sofya Raskhodnikova, and Nithin Varma
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Erasure-resilient sublinear-time graph algorithms. ACM Trans. Comput. Theory , 14(1):1:1--1:22, 2022
2022
-
[23]
Adversarial low degree testing
Dor Minzer and Kai Zhe Zheng. Adversarial low degree testing. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 4395--4409. SIAM , 2024
2024
-
[24]
Tolerant property testing and distance approximation
Michal Parnas, Dana Ron, and Ronitt Rubinfeld. Tolerant property testing and distance approximation. J. Comput. Syst. Sci. , 72(6):1012--1042, 2006
2006
-
[25]
Monotonicity testing
Sofya Raskhodnikova. Monotonicity testing. Masters Thesis, MIT , 1999
1999
-
[26]
Testing if an array is sorted
Sofya Raskhodnikova. Testing if an array is sorted. Encyclopedia of Algorithms , pages 2219--2222, 2016
2016
-
[27]
Strong lower bounds for approximating distribution support size and the distinct elements problem
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science , FOCS '07, page 559–569. IEEE Co...
2007
-
[28]
Erasures versus errors in local decoding and property testing
Sofya Raskhodnikova, Noga Ron - Zewi, and Nithin Varma. Erasures versus errors in local decoding and property testing. Random Structures and Algorithms , 59(4):640--670, 2021
2021
-
[29]
Robust characterizations of polynomials with applications to program testing
Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing (SICOMP) , 25(2):252--271, 1996
1996
-
[30]
Brief announcement: Erasure-resilience versus tolerance to errors
Sofya Raskhodnikova and Nithin Varma. Brief announcement: Erasure-resilience versus tolerance to errors. In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP) , pages 111:1--111:3, 2018
2018
-
[31]
A CLT and tight lower bounds for estimating entropy
Gregory Valiant and Paul Valiant. A CLT and tight lower bounds for estimating entropy. Electron. Colloquium Comput. Complex. , TR10-179 , 2010
2010
-
[32]
New direct sum tests
Alek Westover, Edward Yu, and Kai Zheng. New direct sum tests. CoRR , abs/2409.10464, 2024
2024 arXiv
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.