### Rutgers Discrete Mathematics Seminar

Title: Every locally characterized affine-invariant property is testable

Speaker: **Arnab Bhattacharyya**, DIMACS

Date: Tuesday, January 29, 2013 2:00pm

Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ

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 property 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.

See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math