|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Optimal Testing of Reed-Muller Codes | | Arnab Bhattacharya
; Swastik Kopparty
; Grant Schoenebeck
; Madhu Sudan
; David Zuckerman
; | | Date: |
4 Oct 2009 | | Abstract: | We consider the problem of testing if a given function $f : F_2^n o F_2$
is close to any degree $d$ polynomial in $n$ variables, also known as the
Reed-Muller testing problem. Alon et al. cite{AKKLR} proposed and analyzed a
natural $2^{d+1}$-query test for this property and showed that it accepts every
degree $d$ polynomial with probability 1, while rejecting functions that are
$Omega(1)$-far with probability $Omega(1/(d 2^{d}))$. We give an
asymptotically optimal analysis of their test showing that it rejects functions
that are (even only) $Omega(2^{-d})$-far with $Omega(1)$-probability (so the
rejection probability is a universal constant independent of $d$ and $n$).
Our proof works by induction on $n$, and yields a new analysis of even the
classical Blum-Luby-Rubinfeld cite{BLR} linearity test, for the setting of
functions mapping $F_2^n$ to $F_2$. The optimality follows from a tighter
analysis of counterexamples to the "inverse conjecture for the Gowers norm"
constructed by cite{GT,LMS}.
Our result gives a new relationship between the $(d+1)^{
m{st}}$-Gowers norm
of a function and its maximal correlation with degree $d$ polynomials. For
functions highly correlated with degree $d$ polynomials, this relationship is
asymptotically optimal. Our improved analysis of the cite{AKKLR}-test also
improves the parameters of an XOR lemma for polynomials given by Viola and
Wigderson cite{VW}. Finally, the optimality of our result also implies a
"query-hierarchy" result for property testing of linear-invariant properties:
For every function $q(n)$, it gives a linear-invariant property that is
testable with $O(q(n))$-queries, but not with $o(q(n))$-queries, complementing
an analogous result of cite{GKNR08} for graph properties. | | Source: | arXiv, 0910.0641 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER