Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-054 | 16th April 2006 00:00

Low-degree tests at large distances


Authors: Alex Samorodnitsky
Publication: 24th April 2006 17:19
Downloads: 3000


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.

ISSN 1433-8092 | Imprint