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]