Property Testing with Online Adversaries
CoRR(2023)
摘要
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要