Robust Multiplication-Based Tests for Reed–Muller Codes
Prahladh Harsha, Srikanth Srinivasan · IEEE Transactions on Information Theory · 2018
We consider the following multiplication-based tests to check if a given function f : Fqn→ Fqis a codeword of the Reed-Muller code of dimension n and order d over the finite field Fqfor prime q (i.e., f is the evaluation of a degree-d polynomial over Fq for q prime). Teste,k: pick P1,..., Pkindependent random degree-e polynomials and accept if the function f P1· · · Pkis 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 P1, ..., Pkcan 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 Fq, which may be of independent interest.