## 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 rth-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/∈ + r2^{2r}) positions. On the 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/∈ + 2^{r}) queries.

Original language | English (US) |
---|---|

Pages (from-to) | 4032-4039 |

Number of pages | 8 |

Journal | IEEE Transactions on Information Theory |

Volume | 51 |

Issue number | 11 |

DOIs | |

State | Published - Nov 2005 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Science Applications
- Library and Information Sciences

## Keywords

- Affine subspaces
- Binary field
- Multivariate polynomials
- Property testing
- Reed-Muller code