2011/04/17 by Hamed Hatami, Shachar Lovett, Hatami, Hamed +1
Computer Science · Mathematics · #12Y05 #Analytic Number Theory Research #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1104.3335
openalex publication_date 2011/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Recently there has been much interest in Gowers uniformity norms from the\nperspective of theoretical computer science. This is mainly due to the fact\nthat these norms provide a method for testing whether the maximum correlation\nof a function f: mathbbFpn \→ mathbbFp with polynomials of\ndegree at most d \≤ p is non-negligible, while making only a constant number\nof queries to the function. This is an instance of em correlation testing.\nIn this framework, a fixed test is applied to a function, and the acceptance\nprobability of the test is dependent on the correlation of the function from\nthe property. This is an analog of em proximity oblivious testing, a notion\ncoined by Goldreich and Ron, in the high error regime. In this work, we study\ngeneral properties which are affine invariant and which are correlation\ntestable using a constant number of queries. We show that any such property (as\nlong as the field size is not too small) can in fact be tested by Gowers\nuniformity tests, and hence having correlation with the property is equivalent\nto having correlation with degree d polynomials for some fixed d. We stress\nthat our result holds also for non-linear properties which are affine\ninvariant. This completely classifies affine invariant properties which are\ncorrelation testable. The proof is based on higher-order Fourier analysis.\nAnother ingredient is a nontrivial extension of a graph theoretical theorem of\nErd "os, Lov 'asz and Spencer to the context of additive number theory.\n