Adversarial Low Degree Testing
Dor Minzer, Kai Zheng · Society for Industrial and Applied Mathematics eBooks · 2024
In the t-online-erasure model in property testing, an adversary is allowed to erase t values of a queried function for each query the tester makes. This model was recently formulated by Kalemaj, Raskhodnikova and Varma, who showed that the properties of linearity of functions as well as quadraticity can be tested in Ot (1) many queries: O(log(t)) for linearity and 22O(t) for quadraticity. They asked whether the more general property of low-degreeness can be tested in the online erasure model, whether better testers exist for quadraticity, and if similar results hold when “erasures” are replaced with “corruptions”.