Every locally characterized affine-invariant property is testable

by Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.

Oded's comments

I have mixed feelings towards this paper. I do like some of its results, but do not like the presentation and fear it hinders the impact of the paper.

The main result, as far as I'm concerned, is a characterization of affine-invariant properties that have a proximity-oblivious tester (POT). The characterization asserts that POT exists for such a property if and only if the property can be expressed as satisfaction of a fixed number of local constraints. Interestingly, this characterization is reminiscent of the situation in the "dense graph model" (i.e., testing graph properties in the adjacency matrix representation model): See here.

Another interesting result is a framework for properties of polynomials, which is pivoted at degree structures. This framework captures several natural properties of polynomials such as having non-trivial factors (over the base field) or being a product of linear functions. It is shown that every property in this framework has a POT.

The original abstract

See the proceedings of the 45th STOC. An approximate reproduction follows.

[Let F be a finite field of prime order.] An affine-invariant property is a property of [$n$-variate] functions over F 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 Pi, meaning that given an input function f, we make a constant number of queries to f, always accept if f satisfies Pi, and otherwise reject with probability larger than a positive number that depends only on the distance between f and Pi. 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 low-degree 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 polynomials*. 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 degree-structural properties.


Back to list of Oded's choices.