  The online manipulation-resilient testing model, proposed by Kalemaj,
Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies
property testing in situations where access to the input degrades continuously
and adversarially. Specifically, after each query made by the tester is
answered, the adversary can intervene and either erase or corrupt $t$ data
points. In this work, we investigate a more nuanced version of the online model
in order to overcome old and new impossibility results for the original model.
We start by presenting an optimal tester for linearity and a lower bound for
low-degree testing of Boolean functions in the original model. We overcome the
lower bound by allowing batch queries, where the tester gets a group of queries
answered between manipulations of the data. Our batch size is small enough so
that function values for a single batch on their own give no information about
whether the function is of low degree. Finally, to overcome the impossibility
results of Kalemaj et al. for sortedness and the Lipschitz property of
sequences, we extend the model to include $t<1$, i.e., adversaries that make
less than one erasure per query. For sortedness, we characterize the rate of
erasures for which online testing can be performed, exhibiting a sharp
transition from optimal query complexity to impossibility of testability (with
any number of queries). Our online tester works for a general class of local
properties of sequences. One feature of our results is that we get new (and in
some cases, simpler) optimal algorithms for several properties in the standard
property testing model.
