Apr 4, 3:30pm, Wean 8220

Arnab Bhattacharyya, DIMACS/Rutgers

Every locally characterized affine-invariant property is testable

Arnab Bhattacharyya, DIMACS/Rutgers

Every locally characterized affine-invariant property is testable

Abstract:

Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a
property of functions on F^n 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 there is a
test that, given an input function f, makes a constant number of queries to
f, always accepts if f satisfies P, and rejects with positive probability
if the distance between f and P is nonzero. 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 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.

Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett.