Low-degree tests at large distances

Details Low-degree tests at large distances Low-degree tests at large distances

2006-04-16

arxiv.org/abs/math/0604353v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Low-degree tests at large distances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Low-degree tests at large distances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-degree tests at large distances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241904