[1]   Noga Alon and Michael Luby: A linear time erasure-resilient code with nearly optimal recovery. IEEE Trans. Inform. Theory, 42(6):1732–1736, 1996. Preliminary version by Noga Alon, Jeff Edmonds, and Michael Luby in FOCS’95. [doi:10.1109/18.556669]

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

[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]   Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja: Randomized polynomial-time identity testing for noncommutative circuits. Theory of Computing, 15(7):1–36, 2019. Preliminary version in STOC’17. [doi:10.4086/toc.2019.v015a007]

[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]   Alexander Barg, Itzhak Tamo, and Serge Vlăduţ: Locally recoverable codes on algebraic curves. IEEE Trans. Inform. Theory, 63(8):4928–4939, 2017. Preliminary version in ISIT’15. [doi:10.1109/TIT.2017.2700859, arXiv:1603.08876]

[7]   Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. 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, Oded Lachish, and Arie Matsliah: Sound 3-query PCPPs are long. ACM Trans. Comput. Theory, 1(2):7:1–7:49, 2009. Preliminary version in ICALP’08. [doi:10.1145/1595391.1595394, ECCC:TR07-127]

[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]   Viveck R. Cadambe and Arya Mazumdar: Bounds on the size of locally recoverable codes. IEEE Trans. Inform. Theory, 61(11):5787–5794, 2015. Preliminary version in NetCod’13. [doi:10.1109/TIT.2015.2477406]

[11]   Clément L. Canonne and Tom Gur: An adaptivity hierarchy theorem for property testing. Comput. Complexity, 27(4):671–716, 2018. Preliminary version in CCC’17. [doi:10.1007/s00037-018-0168-4, arXiv:1702.05678]

[12]   Alessandro Chiesa, Tom Gur, and Igor Shinkar: Relaxed locally correctable codes with nearly-linear block length and constant query complexity. In Proc. 31st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’20), pp. 1395–1411. ACM Press, 2020. [doi:10.1137/1.9781611975994.84, ECCC:TR20-113]

[13]   Marcel Dall’Agnol, Tom Gur, and Oded Lachish: A structural theorem for local algorithms with applications to coding, testing, and privacy. Electron. Colloq. on Comput. Complexity (ECCC), TR20-154:1–55, 2020. [ECCC]

[14]   Irit Dinur: The PCP theorem by gap amplification. J. ACM, 54(3):12–55, 2007. Preliminary version in STOC’06. [doi:10.1145/1236457.1236459, ECCC:TR05-046]

[15]   Irit Dinur and Prahladh Harsha: Composition of low-error 2-query PCPs using decodable PCPs. In Oded Goldreich, editor, Property Testing: Current Research and Surveys, volume 6390 of LNCS, pp. 280–288. Springer, 2010. Preliminary version in FOCS’09. [doi:10.1007/978-3-642-16367-8_21]

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

[17]   Klim Efremenko: 3-query locally decodable codes of subexponential length. SIAM J. Comput., 41(6):1694–1703, 2012. Preliminary version in STOC’09. [doi:10.1137/090772721, ECCC:TR08-069]

[18]   Katalin Friedl and Madhu Sudan: Some improvements to total degree tests. In 4th Israel Symp. on Theory of Computing and Systems (ISTCS’95), pp. 190–198. IEEE Comp. Soc., 1995. [doi:10.1109/ISTCS.1995.377032, arXiv:1307.3975]

[19]   Peter Gemmell and Madhu Sudan: Highly resilient correctors for polynomials. Inform. Process. Lett., 43(4):169–174, 1992. [doi:10.1016/0020-0190(92)90195-2]

[20]   Edgar N. Gilbert: A comparison of signalling alphabets. Bell Sys. Tech. J., 31(3):504–522, 1952. [doi:10.1002/j.1538-7305.1952.tb01393.x]

[21]   Oded Goldreich: Bravely, moderately: A common theme in four recent works. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pp. 373–389. Springer, 2011. [doi:10.1007/978-3-642-22670-0_26]

[22]   Oded Goldreich: A sample of samplers: A computational perspective on sampling. In Oded Goldreich, editor, Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pp. 302–332. Springer, 2011. [doi:10.1007/978-3-642-22670-0_24]

[23]   Oded Goldreich: Introduction to Property Testing. Cambridge Univ. Press, 2017. [doi:10.1017/9781108135252]

[24]   Oded Goldreich and Tom Gur: Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Electron. Colloq. on Comput. Complexity (ECCC), 23:1–20, 2016. [ECCC:TR16-192]

[25]   Oded Goldreich and Tom Gur: Universal locally testable codes. Chicago J. Theoret. Comp. Sci., 2018(3):1–21, 2018. [doi:10.4086/cjtcs.2018.003, ECCC:TR16-042]

[26]   Oded Goldreich, Tom Gur, and Ilan Komargodski: Strong locally testable codes with relaxed local decoders. ACM Trans. Comput. Theory, 11(3):17:1–17:38, 2019. Preliminary version in CCC’15. [doi:10.1145/3319907, ECCC:TR14-025]

[27]   Oded Goldreich and Madhu Sudan: Locally testable codes and PCPs of almost-linear length. J. ACM, 53(4):558–655, 2006. Preliminary version in FOCS’02. [doi:10.1145/1162349.1162351, ECCC:TR02-050]

[28]   Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin: On the locality of codeword symbols. IEEE Trans. Inform. Theory, 58(11):6925–6934, 2012. [doi:10.1109/TIT.2012.2208937, arXiv:1106.3625]

[29]   Tom Gur and Oded Lachish: On the power of relaxed local decoding algorithms. In Proc. 31st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’20), pp. 1377–1394. ACM Press, 2020. [doi:10.1137/1.9781611975994.83]

[30]   Tom Gur, Govind Ramnarayan, and Ron D. Rothblum: Relaxed locally correctable codes. In Proc. 9th Innovations in Theoret. Comp. Sci. conf. (ITCS’18), pp. 27:1–27:11. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.27]

[31]   Tom Gur and Ron D. Rothblum: Non-interactive proofs of proximity. Comput. Complexity, 27(1):99–207, 2018. Preliminary version in ITCS’15. [doi:10.1007/s00037-016-0136-9]

[32]   Venkatesan Guruswami, Atri Rudra, and Madhu Sudan: Essential Coding Theory. 2019. Book. Draft available at author’s website.

[33]   Venkatesan Guruswami, Chaoping Xing, and Chen Yuan: How long can optimal locally repairable codes be? IEEE Trans. Inform. Theory, 65(6):3662–3670, 2019. Preliminary version in RANDOM’18. [doi:10.1109/TIT.2019.2891765, arXiv:1807.01064]

[34]   Richard W. Hamming: Error detecting and error correcting codes. Bell Sys. Tech. J., 29(2):147–160, 1950. [doi:10.1002/j.1538-7305.1950.tb00463.x]

[35]   Brett Hemenway, Noga Ron-Zewi, and Mary Wootters: 2017. Personal communication.

[36]   Jørn Justesen: Class of constructive asymptotically good algebraic codes. IEEE Trans. Inform. Theory, 18(5):652–656, 1972. [doi:10.1109/TIT.1972.1054893]

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

[38]   Swastik Kopparty and Shubhangi Saraf: Local testing and decoding of high-rate error-correcting codes. Electron. Colloq. on Comput. Complexity (ECCC), TR17-126:1–21, 2017. A version of this paper appeared in SIGACT News. [ECCC]

[39]   Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146605]

[40]   Or Meir: Combinatorial construction of locally testable codes. SIAM J. Comput., 39(2):491–544, 2009. Preliminary version in STOC’08. [doi:10.1137/080729967]

[41]   Or Meir: Combinatorial PCPs with short proofs. Comput. Complexity, 25(1):1–102, 2016. Preliminary version in CCC’12. [doi:10.1007/s00037-015-0111-x, ECCC:TR13-134]

[42]   Dana Moshkovitz and Ran Raz: Two-query PCP with subconstant error. J. ACM, 57(5):29:1–29:29, 2010. Preliminary version in FOCS’08. [doi:10.1145/1754399.1754402, ECCC:TR08-071]

[43]   Omer Reingold: Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, 2008. Preliminary version in STOC’05. [doi:10.1145/1391289.1391291, ECCC:TR04-094]

[44]   Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum: Constant-round interactive proofs for delegating computation. In Proc. 48th STOC, pp. 49–62. ACM Press, 2016. [doi:10.1145/2897518.2897652, ECCC:TR16-061]

[45]   Omer Reingold, Salil P. Vadhan, and Avi Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Ann. Math., 155(1):157–187, 2002. Preliminary version in FOCS’00. [doi:10.2307/3062153, arXiv:math/0406038, ECCC:TR01-018]

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

[47]   Claude Elwood Shannon: Communication in the presence of noise. Proc. IRE, 37(1):10–21, 1949. [doi:10.1109/JRPROC.1949.232969]

[48]   Madhu Sudan: Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems. Springer, 1995. [doi:10.1007/3-540-60615-7]

[49]   Itzhak Tamo and Alexander Barg: A family of optimal locally recoverable codes. IEEE Trans. Inform. Theory, 60(8):4661–4676, 2014. Preliminary version in ISIT’14. [doi:10.1109/TIT.2014.2321280, arXiv:1311.3284]

[50]   Paul Valiant: The tensor product of two codes is not necessarily robustly testable. In Proc. 9th Internat. Workshop on Randomization and Computation (RANDOM’05), pp. 472–481. Springer, 2005. [doi:10.1007/11538462_40]

[51]   Rom R. Varshamov: Estimate of the number of signals in error correcting codes. In Dokl. Akad. Nauk SSSR (Russian), volume 117, pp. 739–741, 1957.

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

[53]   Sergey Yekhanin: Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):1:1–1:16, 2008. Preliminary version in STOC’07. [doi:10.1145/1326554.1326555]

[54]   Sergey Yekhanin: Locally decodable codes. Found. Trends Theor. Comp. Sci., 6(3):139–255, 2012. [doi:10.1561/0400000030]

[55]   Victor Vasilievich Zyablov: An estimate of the complexity of constructing binary linear cascade codes (Russian). Problemy Peredachi Informatsii, 7(1):5–13, 1971. Link at Mathnet.ru English translation: Probl. Inform. Transmission 7(1) (1971) 3–10.