Property Testing with Online Adversaries

The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova, and Varma (Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Our main contributions are as follows: — An extension of the model, introducing batch queries where multiple queries are made and answered between each round of manipulation, and fractional manipulation rate , where the adversary makes less than one manipulation per round. — New optimal testers for linearity of Boolean functions in the original online and offline models. — A new lower bound in the original model for testing whether a Boolean function has low degree and an algorithm using batch queries that overcomes it. — Efficient testers for local properties of sequences when the manipulation rate is fractional. Specifically, for sortedness, we show a sharp transition from optimal query complexity to the impossibility of testability, depending on the manipulation rate.