From Local to Robust Testing via Agreement Testing

by Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi

Theory of Computing, Volume 18(12), pp. 1-25, 2022

Bibliography with links to cited articles

[1]   Sanjeev Arora: Probabilistic Checking of Proofs and the Hardness of Approximation Problems. Ph. D. thesis, UC Berkeley, 1994. ECCC.

[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. [doi:10.1145/278298.278306, ECCC:TR98-008]

[3]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70–122, 1998. Preliminary version in FOCS’92. [doi:10.1145/273865.273901]

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

[5]   László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy: Checking computations in polylogarithmic time. In Proc. 23rd STOC, pp. 21–31. ACM Press, 1991. [doi:10.1145/103418.103428]

[6]   László Babai, Lance Fortnow, and Carsten Lund: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity, 1(1):3–40, 1991. Preliminary version in FOCS’90. [doi:10.1007/BF01200056]

[7]   Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan: Robust PCPs of proximity, shorter PCPs and applications to coding. SIAM J. Comput., 36(4):889–974, 2006. Preliminary version in STOC’04. [doi:10.1137/S0097539705446810, ECCC:TR04-021]

[8]   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. [doi:10.1137/S0097539704445445]

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

[10]   Eli Ben-Sasson and Madhu Sudan: Robust locally testable codes and products of codes. Random Struct. Algor., 28(4):387–402, 2006. Preliminary version in RANDOM’04. [doi:10.1002/rsa.20120, arXiv:cs/0408066, ECCC:TR04-046]

[11]   Eli Ben-Sasson and Michael Viderman: Composition of semi-LTCs by two-wise tensor products. Comput. Complexity, 24(3):601–643, 2015. Preliminary version in RANDOM’09. [doi:10.1007/s00037-013-0074-8, ECCC:TR11-070]

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

[13]   Yotam Dikstein and Irit Dinur: Agreement testing theorems on layered set systems. In Proc. 60th FOCS, pp. 1495–1524. IEEE Comp. Soc., 2019. [doi:10.1109/FOCS.2019.00088, arXiv:1909.00638, ECCC:TR19-112]

[14]   Irit Dinur and Elazar Goldenberg: Locally testing direct product in the low error range. In Proc. 49th FOCS, pp. 613–622. IEEE Comp. Soc., 2008. [doi:10.1109/FOCS.2008.26]

[15]   Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi: From local to robust testing via agreement testing. In Proc. 10th Innovations in Theoret. Comp. Sci. conf. (ITCS’19), pp. 29:1–18. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.29]

[16]   Irit Dinur and Tali Kaufman: High dimensional expanders imply agreement expanders. In Proc. 58th FOCS, pp. 974–985. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.94, ECCC:TR17-089]

[17]   Irit Dinur and Inbal Livni Navon: Exponentially small soundness for the direct product Z-test. In Proc. 32nd Comput. Complexity Conf. (CCC’17), pp. 29:1–29:50. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.CCC.2017.29, ECCC:TR17-096]

[18]   Irit Dinur and Omer Reingold: Assignment testers: Towards a combinatorial proof of the PCP Theorem. SIAM J. Comput., 36(4):975–1024, 2006. Preliminary version in FOCS’04. [doi:10.1137/S0097539705446962]

[19]   Irit Dinur and David Steurer: Direct product testing. In Proc. 29th IEEE Conf. on Comput. Complexity (CCC’14), pp. 188–196. IEEE Comp. Soc., 2014. [doi:10.1109/CCC.2014.27, ECCC:TR13-179]

[20]   Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy: Interactive proofs and the hardness of approximating cliques. J. ACM, 43(2):268–292, March 1996. Preliminary version in FOCS’91. [doi:10.1145/226643.226652]

[21]   Peter Gemmell, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan, and Avi Wigderson: Self-testing/correcting for polynomials and for approximate functions. In Proc. 23rd STOC, pp. 32–42. ACM Press, 1991. [doi:10.1145/103418.103429]

[22]   Oded Goldreich and Shmuel Safra: A combinatorial consistency lemma with application to proving the PCP theorem. SIAM J. Comput., 29(4):1132–1154, 2000. Preliminary version in RANDOM’97. [doi:10.1137/S0097539797315744, ECCC:TR96-047]

[23]   Alan Guo, Elad Haramaty, and Madhu Sudan: Robust testing of lifted codes with applications to low-degree testing. In Proc. 56th FOCS, pp. 825–844. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.56, ECCC:TR15-043]

[24]   Alan Guo, Swastik Kopparty, and Madhu Sudan: New affine-invariant codes from lifting. In Proc. 4th Innovations in Theoret. Comp. Sci. conf. (ITCS’13), pp. 529–540. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2013. [doi:10.1145/2422436.2422494, arXiv:1208.5413, ECCC:TR12-149]

[25]   Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan: Absolutely sound testing of lifted codes. Theory of Computing, 11(12):299–338, 2015. Preliminary version in RANDOM’13. [doi:10.4086/toc.2015.v011a012, ECCC:TR13-030]

[26]   Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson: Uniform direct product theorems: Simplified, optimized, and derandomized. SIAM J. Comput., 39(4):1637–1665, 2010. Preliminary version in STOC’08. [doi:10.1137/080734030, ECCC:TR08-079]

[27]   Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson: New direct-product testers and 2-query PCPs. SIAM J. Comput., 41(6):1722–1768, 2012. Preliminary version in STOC’09. [doi:10.1137/09077299X, ECCC:TR09-090]

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

[29]   Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf: High-rate locally correctable and locally testable codes with sub-polynomial query complexity. J. ACM, 64(2):11:1–11:42, 2017. Preliminary version in STOC’16. [doi:10.1145/3051093, arXiv:1504.05653, ECCC:TR15-068]

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

[31]   Ronitt Rubinfeld and Madhu Sudan: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996. Preliminary versions in STOC’91 and SODA’92. [doi:10.1137/S0097539793255151]

[32]   Michael Viderman: A combination of testability and decodability by tensor products. Random Struct. Algor., 46(3):572–598, 2015. Preliminary version in RANDOM’12. [doi:10.1002/rsa.20498, arXiv:1105.5806, ECCC:TR11-087]