2013/06/04 by Hamed Hatami, Shachar Lovett, Hatami, Hamed +1
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1306.0649
openalex publication_date 2013/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let \calP be an affine invariant property of functions \mathbbFpn → [R] for fixed p and R. We show that if \calP is locally testable with a constant number of queries, then one can estimate the distance of a function f from \calP with a constant number of queries. This was previously unknown even for simple properties such as cubic polynomials over \mathbbF2. Our test is simple: take a restriction of f to a constant dimensional affine subspace, and measure its distance from \calP. We show that by choosing the dimension large enough, this approximates with high probability the global distance of f from \cP. 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].