Let P be an affine invariant property of functions F n p → [R] for fixed p and R. We show that if P is locally testable with a constant number of queries, then one can estimate the distance of a function f from P with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over F 2 . Our test is simple: take a restriction of f to a constant dimensional affine subspace, and measure its distance from P. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from P. The analysis combines the approach of Fischer and Newman [SIAM J. Comp 2007] who established a similar result for graph properties, with recently developed tools in higher order Fourier analysis, in particular those developed in Bhattacharyya et al. [STOC 2013].
Recently, Hatami and Lovett REF showed that, if an affine property P is locally testable, then the distance to P can be estimated with a constant number of queries.
Estimating the Distance from Testable Affine-Invariant Properties
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
2013 IEEE 54th Annual Symposium on Foundations of Computer Science
Mathematics Computer Science