Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-184 | 20th January 2013 03:07

Every locally characterized affine-invariant property is testable.

RSS-Feed




Revision #1
Authors: Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett
Accepted on: 20th January 2013 03:07
Downloads: 4551
Keywords: 


Abstract:

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{F}^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property $\mathcal{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 $\mathcal{P}$, and rejects with positive probability if the distance between $f$ and $\mathcal{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.



Changes to previous version:

Added references and improved writing.


Paper:

TR12-184 | 26th December 2012 19:45

Every locally characterized affine-invariant property is testable.





TR12-184
Authors: Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett
Publication: 26th December 2012 21:52
Downloads: 3125
Keywords: 


Abstract:

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{F}^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property $\mathcal{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 $\mathcal{P}$, and rejects with positive probability if the distance between $f$ and $\mathcal{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.



ISSN 1433-8092 | Imprint