__
TR06-054 | 16th April 2006 00:00
__

#### Low-degree tests at large distances

**Abstract:**
We define tests of boolean functions which

distinguish between linear (or quadratic) polynomials, and functions

which are very far, in an appropriate sense, from these

polynomials. The tests have optimal or nearly optimal trade-offs

between soundness and the number of queries.

In particular, we show that functions with small Gowers uniformity

norms behave ``randomly'' with respect to hypergraph linearity tests.

A central step in our analysis of quadraticity tests is the proof of an

inverse theorem for the third Gowers uniformity norm of boolean functions.

The last result has also a coding theory application. It is

possible to estimate efficiently the distance from the second-order

Reed-Muller code on inputs lying far beyond its list-decoding radius.