Testing Reed-Muller codes

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

Research output: Contribution to journalArticlepeer-review

92 Scopus citations

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 = 2m is a word in the rth-order Reed-Muller code R(r, m) of length n = 2m. For a given integer r ≥ 1, and real ∈ > 0, the algorithm queries the input vector v at O(1/∈ + r22r) 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/∈ + 2r) queries.

Original languageEnglish (US)
Pages (from-to)4032-4039
Number of pages8
JournalIEEE Transactions on Information Theory
Volume51
Issue number11
DOIs
StatePublished - Nov 2005

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

Fingerprint Dive into the research topics of 'Testing Reed-Muller codes'. Together they form a unique fingerprint.

Cite this