LIPIcs.FSTTCS.2016.17.pdf
- Filesize: 0.53 MB
- 14 pages
Document
Robust Multiplication-Based Tests for Reed-Muller Codes
Authors
-
Part of:
Volume:
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-12-10
Cite As Get BibTex
Prahladh Harsha and Srikanth Srinivasan. Robust Multiplication-Based Tests for Reed-Muller Codes. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FSTTCS.2016.17
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.
Subject Classification
Keywords
- Polynomials over finite fields
- Schwartz-Zippel lemma
- Low degree testing
- Low degree long code
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032-4039, 2005. (Preliminary version in 7th RANDOM, 2003). URL: http://dx.doi.org/10.1109/TIT.2005.856958.
- Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer. Making the long code shorter. SIAM J. Comput., 44(5):1287-1324, 2015. (Preliminary version in 53rd FOCS, 2012). http://arxiv.org/abs/1111.0405, URL: http://dx.doi.org/10.1137/130929394.
- Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of Reed-Muller codes. In Proc. 51st IEEE Symp. on Foundations of Comp. Science (FOCS), pages 488-497, 2010. http://arxiv.org/abs/0910.0641, URL: http://dx.doi.org/10.1109/FOCS.2010.54.
- Irit Dinur and Venkatesan Guruswami. PCPs via the low-degree long code and hardness for constrained hypergraph coloring. Israel Journal of Mathematics, 209:611-649, 2015. (Preliminary version in 54th FOCS, 2013). URL: http://dx.doi.org/10.1007/s11856-015-1231-3.
- Venkat Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, and Girish Varma. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes. In Proc. 46th ACM Symp. on Theory of Computing (STOC), pages 614-623, 2014. http://arxiv.org/abs/1311.7407, URL: http://dx.doi.org/10.1145/2591796.2591882.
- Elad Haramaty, Amir Shpilka, and Madhu Sudan. Optimal testing of multivariate polynomials over small prime fields. SIAM J. Comput., 42(2):536-562, 2013. (Preliminary version in 52nd FOCS, 2011). URL: http://dx.doi.org/10.1137/120879257.
- Sangxia Huang. 2^(log N)^1/10-o(1) hardness for hypergraph coloring. (manuscript), 2015. URL: http://arxiv.org/abs/1504.03923.
- Tadao Kasami, Shu Lin, and W. Wesley Peterson. Polynomial codes. IEEE Trans. Inform. Theory, 14(6):807-814, 1968. URL: http://dx.doi.org/10.1109/TIT.1968.1054226.
- Subhash Khot and Rishi Saket. Hardness of coloring 2-colorable 12-uniform hypergraphs with 2^(log n)^Ω(1) colors. In Proc. 55th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 206-215, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.30.
- Girish Varma. Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. Chicago J. Theor. Comput. Sci., 2015(3):1-8, 2015. http://arxiv.org/abs/1408.0262, URL: http://dx.doi.org/10.4086/cjtcs.2015.003.