Property Testing with Online Adversaries

Abstract

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 \emph{batch queries} where multiple queries are made and answered between each round of manipulation, and \emph{fractional manipulation rate}, where the adversary makes less than one manipulation per round. - New optimal testers for linearity testing of Boolean functions in the original online and offline models. - A new lower-bound for testing low-degree of Boolean functions in the original model which can be overcome by an algorithm using batch queries. - 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.