ECCC-Report TR06-054https://eccc.weizmann.ac.il/report/2006/054Comments and Revisions published for TR06-054en-usMon, 24 Apr 2006 17:19:40 +0300
Paper TR06-054
| Low-degree tests at large distances |
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2006/054We 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.
Mon, 24 Apr 2006 17:19:40 +0300https://eccc.weizmann.ac.il/report/2006/054