| Testing Reed Muller Codes ∗ (2009) | |||||||||||||||
Abstract | |||||||||||||||
| A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector’s bits. We show that the Reed-Muller codes of constant order are locally testable. Specifically, we describe an efficient randomized algorithm to test if a given vector of length n = 2 m is a word in the r-th order Reed-Muller code R(r, m) of length n = 2 m. For a given integer r ≥ 1, and real ɛ> 0, the algorithm queries the input vector v at O ( 1 ɛ + r22r) positions. On one hand, if v is at distance at least ɛn from the closest codeword, then the algorithm discovers it with probability at least 2/3. On the other hand, if v is a codeword, then it always passes the test. Our result is almost tight: any algorithm for testing R(r, m) must perform Ω ( 1 ɛ + 2r) queries. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||