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

Testing Low-Degree Polynomials Over Prime Fields

Abstract : Much recent research in computational complexity has been due to the concept of Probabilistically Checkable Proofs (PCPs). Perhaps the most striking application of PCPs has been in proving limitations for approximating certain NP-hard problems. Interestingly, most of these PCPs use error-correcting codes. In particular they require the following property of the code: given a received word, one has to determine (with high probability) whether it is indeed a codeword or far from being one while looking at very few positions of the received word. Codes with local testers that can efficiently compute the above approximate answers are called locally testable codes (LTCs). Amazingly, such testers exist that can perform this task by looking at only a constant number of positions.

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.