UC San Diego

Let P be an affine invariant property of multivariate functions over a constant size finite field. 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 the binary field. 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]. Copyright © 2013 by The Institute of Electrical and Electronics Engineers, Inc.