Robust multiplication-based tests for reed–muller codes

Abstract

We consider the following multiplication-based tests to check if a given function f : Fⁿ_q → F_q is a codeword of the Reed-Muller code of dimension n and order d over the finite field F_q for prime q (i.e., f is the evaluation of a degree-d polynomial over F_q for q prime). Test_e,k: pick P₁,..., P_k independent random degree-e polynomials and accept if the function f P₁ · · · P_k is the evaluation of a degree-(d + ek) polynomial (i.e., is a codeword of the Reed-Muller code of dimension n and order (d + ek)). We prove the robust soundness of the abovementioned tests for large values of e, answering a question of Dinur and Guruswami. Previous soundness analyses of these tests were known only for the case when either e = 1 or k = 1. Even for the case k = 1 and e > 1, earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials P₁, ..., P_k can be the same random polynomial P. This generalizes a result of Guruswami et al. One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields F_q, which may be of independent interest.