Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra and David Zuckerman

One of the most important codes in this context are
*Reed-Muller codes*. These codes are generalizations of Reed-Solomon
codes, which have played an important roles in the recent progress in list
decoding. Local
testers for Reed-Muller codes formed an integral part of the proof of the
famous PCP theorem. However, almost all previous results dealt with
Reed-Muller codes for the case when the degree parameter was smaller
than
the size of the alphabet on which the code is defined. However, Reed-Muller
codes that have more practical applications operate in the *opposite*
regime-- the degree parameter is greater than the size of the alphabet.
In this work we designed efficient local testers for Reed-Muller codes
that operate in the regime of practical interest mentioned above. The number
of queries that our testers make is almost optimal.

- In the Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Pgs 423-432. October 2004. [PDF]