A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes

by Noga Ron-Zewi and Madhu Sudan

Theory of Computing, Volume 9(25), pp. 783-807, 2013

Bibliography with links to cited articles

[1]   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 RANDOM’03. [doi:10.1109/TIT.2005.856958]

[2]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and the hardness of approximation problems. J. ACM, 45(3):501–555, 1998. Preliminary version in FOCS’92. See also at ECCC. [doi:10.1145/278298.278306]

[3]   Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, and David Steurer: Making the long code shorter. In Proc. 53rd FOCS, pp. 370–379. IEEE Comp. Soc. Press, 2012. See also at ECCC. [doi:10.1109/FOCS.2012.83]

[4]   Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, and Madhu Sudan: On sums of locally testable affine invariant properties. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11), pp. 400–411. Springer, 2011. See also at ECCC. [doi:10.1007/978-3-642-22935-0_34]

[5]   Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova: Some 3CNF properties are hard to test. SIAM J. Comput., 35(1):1–21, 2005. Preliminary version in STOC’03. See also at ECCC. [doi:10.1137/S0097539704445445]

[6]   Eli Ben-Sasson and Madhu Sudan: Limits on the rate of locally testable affine-invariant codes. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11), pp. 412–423. Springer, 2011. See also at ECCC. [doi:10.1007/978-3-642-22935-0_35]

[7]   Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman: Optimal testing of Reed-Muller codes. In Proc. 51st FOCS, pp. 488–497. IEEE Comp. Soc. Press, 2010. See also at ECCC and an overview in “Property Testing” (Springer 2011). [doi:10.1109/FOCS.2010.54]

[8]   Peng Ding and Jennifer D. Key: Minimum-weight codewords as generators of generalized Reed-Muller codes. IEEE Trans. Inform. Theory, 46(6):2152–2158, 2000. [doi:10.1109/18.868484]

[9]   Katalin Friedl and Madhu Sudan: Some improvements to total degree tests. In Proc. 3rd Ann. Israel Symp. on Theory of Computing and Systems (ISTCS’95), pp. 190–198. IEEE Comp. Soc. Press, 1995. See corrected version on the arXiv. [doi:10.1109/ISTCS.1995.377032]

[10]   Elena Grigorescu, Tali Kaufman, and Madhu Sudan: Succinct representation of codes with applications to testing. SIAM J. Discrete Math., 26(4):1618–1634, 2012. Preliminary version in RANDOM’09. See also at ECCC. [doi:10.1137/100818364]

[11]   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 FOCS’11. See also at ECCC. [doi:10.1137/120879257]

[12]   Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, and David Zuckerman: Testing low-degree polynomials over prime fields. Random Structures & Algorithms, 35(2):163–193, 2009. Preliminary version in FOCS’04. [doi:10.1002/rsa.20262]

[13]   Tali Kaufman and Dana Ron: Testing polynomials over general fields. SIAM J. Comput., 36(3):779–802, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539704445615]

[14]   Tali Kaufman and Madhu Sudan: Algebraic property testing: The role of invariance. Electron. Colloq. on Comput. Complexity (ECCC), 14(111), 2007. ECCC.

[15]   Tali Kaufman and Madhu Sudan: Algebraic property testing: the role of invariance. In Proc. 40th STOC, pp. 403–412. ACM Press, 2008. See also at ECCC. [doi:10.1145/1374376.1374434]

[16]   Ernst Eduard Kummer: Über die hypergeometrische Reihe. Journal für die reine und angewandte Mathematik, 15:39–83, 1836. EUDML.

[17]   Ronitt Rubinfeld and Madhu Sudan: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. [doi:10.1137/S0097539793255151]

[18]   Emanuele Viola and Avi Wigderson: Norms, XOR lemmas, and lower bounds for polynomials and protocols. Theory of Computing, 4(7):137–168, 2008. Preliminary version in CCC’07. [doi:10.4086/toc.2008.v004a007]