ECCC-Report TR16-204https://eccc.weizmann.ac.il/report/2016/204Comments and Revisions published for TR16-204en-usThu, 22 Dec 2016 09:35:09 +0200
Paper TR16-204
| Robust Multiplication-based Tests for Reed-Muller Codes |
Prahladh Harsha,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2016/204We consider the following multiplication-based tests to check if a given function $f: \mathbb{F}_q^n\to \mathbb{F}_q$ is the evaluation of a degree-$d$ polynomial over $\mathbb{F}_q$ for $q$ prime.
* $\mathrm{Test}_{e,k}$: Pick $P_1,\ldots,P_k$ independent random degree-$e$ polynomials and accept iff the function $fP_1\cdots 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,\ldots,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 $\mathbb{F}_q$, which may be of independent interest.Thu, 22 Dec 2016 09:35:09 +0200https://eccc.weizmann.ac.il/report/2016/204