Testing Reed–Muller Codes

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/sup m/ is a word in the rth-order Reed-Muller code R(r,m) of length n=2/sup m/. For a given integer r/spl ges/1, and real /spl epsi/>0, the algorithm queries the input vector /spl upsi/ at O(1//spl epsi/+r2/sup 2r/) positions. On the one hand, if /spl upsi/ is at distance at least /spl epsi/n from the closest codeword, then the algorithm discovers it with probability at least 2/3. On the other hand, if /spl upsi/ is a codeword, then it always passes the test. Our result is almost tight: any algorithm for testing R(r,m) must perform /spl Omega/(1//spl epsi/+2/sup r/) queries.