Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function f : np → Fp with polynomials of degree at most d ≤ p is nonnegligible, while making only a constant number of queries to the function. This is an instance of correlation testing . In this framework, a fixed test is applied to a function, and the acceptance probability of the test is dependent on the correlation of the function from the property. This is an analogue of proximity oblivious testing, a notion coined by Goldreich and Ron, in the high error regime. In this work, we study general properties which are affine invariant and which are correlation testable using a constant number of queries. We show that any such property (as long as the field size is not too small) can in fact be tested by Gowers uniformity tests, and hence having correlation with the property is equivalent to having correlation with degree d polynomials for some fixed d. We stress that our result holds also for nonlinear properties which are affine invariant. This completely classifies affine invariant properties which are correlation testable. The proof is based on higher-order Fourier analysis. Another ingredient is a nontrivial extension of a graph theoretical theorem of Erd̈os, Lov́asz, and Spencer to the context of additive number theory. © 2014 Society for Industrial and Applied Mathematics.

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.

Higher-order Fourier analysis is a powerful tool that can be used to analyze the densities of linear systems (such as arithmetic progressions) in subsets of Abelian groups. We are interested in the group Fpn, for fixed p and large n, where it is known that analyzing these averages reduces to understanding the joint distribution of a family of sufficiently pseudorandom (formally, high-rank) nonclassical polynomials applied to the corresponding system of linear forms.In this work, we give a complete characterization for these distributions for arbitrary systems of linear forms. This extends previous works which accomplished this in some special cases. As an application, we resolve a conjecture of Gowers and Wolf on the true complexity of linear systems. Our proof deviates from that of the previously known special cases and requires several new ingredients. One of which, which may be of independent interest, is a new theory of homogeneous nonclassical polynomials.

Let f : {0, 1}n → {0, 1} be a boolean function. Its associated XOR function is the two-party function f(x, y) = f(x y). We show that, up to polynomial factors, the deterministic communication complexity of f is equal to the parity decision tree complexity of f. This relies on a novel technique of entropy reduction for protocols, combined with existing techniques in Fourier analysis and additive combinatorics.

Set F = Fp for any fixed prime p ≥ 2. An affine-invariant property is a property of functions over Fn that is closed under taking affine transformations of the domain. We prove that all affine-invariant properties having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that given an input function f, we make a constant number of queries to f, always accept if f satisfies P, and otherwise reject with probability larger than a positive number that depends only on the distance between f and P. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of lowdegree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of a small number of low-degree non-classical polynomi- als. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degreestructural properties. Copyright 2013 ACM.