Mathematics – Combinatorics
Scientific paper
2006-04-16
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.
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-241904