2026-07-21T23:18:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6852 2024-03-06T10:39:02Z ddc:004 open_access

Robust Multiplication-Based Tests for Reed-Muller Codes Harsha, Prahladh Srinivasan, Srikanth Polynomials over finite fields Schwartz-Zippel lemma Low degree testing Low degree long code We consider the following multiplication-based tests to check if a given function f: F^n_q -> F_q is the evaluation of a degree-d polynomial over F_q for q prime. Test_{e,k}: Pick P_1,...,P_k independent random degree-e polynomials and accept iff the function f P_1 ... P_k is the evaluation of a degree-(d + ek) polynomial. We prove the robust soundness of the above tests for large values of e, answering a question of Dinur and Guruswami (FOCS 2013). 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_1 ,... , P_k can be the same random polynomial P. This generalizes a result of Guruswami et al. (STOC 2014). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prahladh Harsha and Srikanth Srinivasan 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.17 urn:nbn:de:0030-drops-68524 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.17 eng https://creativecommons.org/licenses/by/3.0/legalcode