License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.17
URN: urn:nbn:de:0030-drops-68524
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6852/
Harsha, Prahladh ;
Srinivasan, Srikanth
Robust Multiplication-Based Tests for Reed-Muller Codes
Abstract
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.
BibTeX - Entry
@InProceedings{harsha_et_al:LIPIcs:2016:6852,
author = {Prahladh Harsha and Srikanth Srinivasan},
title = {{Robust Multiplication-Based Tests for Reed-Muller Codes}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {17:1--17:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6852},
URN = {urn:nbn:de:0030-drops-68524},
doi = {10.4230/LIPIcs.FSTTCS.2016.17},
annote = {Keywords: Polynomials over finite fields, Schwartz-Zippel lemma, Low degree testing, Low degree long code}
}
|
Keywords: |
|
Polynomials over finite fields, Schwartz-Zippel lemma, Low degree testing, Low degree long code |
|
Collection: |
|
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.12.2016 |
