Absolutely Sound Testing of Lifted Codes

by Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan

Theory of Computing, Volume 11(12), pp. 299-338, 2015

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

[2]   Sanjeev Arora and Madhu Sudan: Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003. Preliminary version in STOC’97 and ECCC. [doi:10.1007/s00493-003-0025-0]

[3]   Boaz Barak, Parikshit Gopalan, Johan HÃ¥stad, Raghu Meka, Prasad Raghavendra, and David Steurer: Making the long code shorter, with applications to the unique games conjecture. In Proc. 53rd FOCS. IEEE Comp. Soc. Press, 2012. Preliminary version in 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. Available at author’s website and ECCC. [doi:10.1007/978-3-642-22935-0_34]

[5]   Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, and Madhu Sudan: Symmetric LDPC codes are not necessarily locally testable. In Proc. 26th IEEE Conf. on Computational Complexity (CCC’11), pp. 55–65. IEEE Comp. Soc. Press, 2011. Preliminary version in ECCC. [doi:10.1109/CCC.2011.14]

[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), volume 6845 of Lecture Notes in Computer Science, pp. 412–423. Springer, 2011. Preliminary version in ECCC. [doi:10.1007/978-3-642-22935-0_35]

[7]   Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar Lovett: Every locally characterized affine-invariant property is testable. In Proc. 45th STOC, pp. 429–436. ACM Press, 2013. Preliminary version in ECCC. [doi:10.1145/2488608.2488662]

[8]   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. Available at ITCS’10 and ECCC. [doi:10.1109/FOCS.2010.54]

[9]   Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version in STOC’90. [doi:10.1016/0022-0000(93)90044-W]

[10]   Hillel Furstenberg and Yitzhak Katznelson: A density version of the Hales-Jewett theorem. J. d’Analyse Math., 57(1):64–119, 1991. [doi:10.1007/BF03041066]

[11]   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 versions in RANDOM’09 and ECCC. [doi:10.1137/100818364]

[12]   Elena Grigorescu, Tali Kaufman, and Madhu Sudan: 2-Transitivity is insufficient for local testability. Comput. Complexity, 22(1):137–158, 2013. Preliminary version in CCC’08. [doi:10.1007/s00037-012-0055-3]

[13]   Alan Guo, Swastik Kopparty, and Madhu Sudan: New affine-invariant codes from lifting. Electron. Colloq. on Comput. Complexity (ECCC), TR12-019, 2012.

[14]   Alan Guo, Swastik Kopparty, and Madhu Sudan: New affine-invariant codes from lifting. In ITCS’13, pp. 529–540, 2013. Preliminary version in ECCC. [doi:10.1145/2422436.2422494]

[15]   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 versions in FOCS’11 and ECCC. [doi:10.1137/120879257]

[16]   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]

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

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

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

[20]   D. H. J. Polymath: A new proof of the density Hales-Jewett theorem. Ann. Math., 175(3):1283–1327, 2012. Preliminary version in CoRR. [doi:10.4007/annals.2012.175.3.6]

[21]   Ran Raz and Shmuel Safra: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM Press, 1997. [doi:10.1145/258533.258641]

[22]   Noga Ron-Zewi and Madhu Sudan: A new upper bound on the query complexity of testing generalized Reed-Muller codes. Theory of Computing, 9(25):783–807, 2013. Preliminary version in RANDOM’12. [doi:10.4086/toc.2013.v009a025]

[23]   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]