[1]   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 versions in FOCS’92 and ECCC. [doi:10.1145/278298.278306]

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

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

[4]   László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complexity, 3(4):307–318, 1993. Preliminary version in SCT’91. [doi:10.1007/BF01275486]

[5]   Boaz Barak, Zeev Dvir, Amir Yehudayoff, and Avi Wigderson: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. In Proc. 43rd STOC, pp. 519–528. ACM Press, 2011. [doi:10.1145/1993636.1993705, arXiv:1009.4375]

[6]   Franck Barthe: On a reverse form of the Brascamp-Lieb inequality. Inventiones Math., 134(2):335–361, 1998. [doi:10.1007/s002220050267, arXiv:math/9705210]

[7]   Donald Beaver and Joan Feigenbaum: Hiding instances in multioracle queries. In Proc. 7th Symp. Theoretical Aspects of Comp. Sci. (STACS’90), volume 415 of LNCS, pp. 37–48. Springer, 1990. [doi:10.1007/3-540-52282-4_30]

[8]   Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, and Shubhangi Saraf: Tight lower bounds for 2-query LCCs over finite fields. Combinatorica, 36(1):1–36, 2016. Preliminary version in FOCS’11. [doi:10.1007/s00493-015-3024-z]

[9]   Manuel Blum and Sampath Kannan: Designing programs that check their work. J. ACM, 42(1):269–291, 1995. Preliminary version in STOC’89. [doi:10.1145/200836.200880]

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

[11]   Benny Chor, Eyal Kushilevitz, Oded Goldreich, and Madhu Sudan: Private information retrieval. J. ACM, 45(6):965–981, 1998. Preliminary version in FOCS’95. [doi:10.1145/293347.293350]

[12]   Zeev Dvir: On matrix rigidity and locally self-correctable codes. Comput. Complexity, 20(2):367–388, 2011. Preliminary version in CCC’10. [doi:10.1007/s00037-011-0009-1]

[13]   Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin: Matching vector codes. SIAM J. Comput., 40(4):1154–1178, 2011. Preliminary version in FOCS’10. [doi:10.1137/100804322]

[14]   Zeev Dvir, Shubhangi Saraf, and Avi Wigderson: Breaking the quadratic barrier for 3-LCC’s over the reals. In Proc. 46th STOC, pp. 784–793. ACM Press, 2014. [doi:10.1145/2591796.2591818, arXiv:1311.5102]

[15]   Zeev Dvir, Shubhangi Saraf, and Avi Wigderson: Improved rank bounds for design matrices and a new proof of Kelly’s theorem. Forum of Math., Sigma, 2(4), 2014. [doi:10.1017/fms.2014.2, arXiv:1211.0330]

[16]   Zeev Dvir and Amir Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. SIAM J. Comput., 36(5):1404–1434, 2007. Preliminary version in STOC’05. [doi:10.1137/05063605X]

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

[18]   Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, and Luca Trevisan: Lower bounds for linear locally decodable codes and private information retrieval. Comput. Complexity, 15(3):263–296, 2006. Preliminary version in CCC’02. [doi:10.1007/s00037-006-0216-3]

[19]   Jonathan Katz and Luca Trevisan: On the efficiency of local decoding procedures for error-correcting codes. In Proc. 32nd STOC, pp. 80–86. ACM Press, 2000. [doi:10.1145/335305.335315]

[20]   Neeraj Kayal and Shubhangi Saraf: Blackbox polynomial identity testing for depth 3 circuits. In Proc. 50th FOCS, pp. 198–207. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.67]

[21]   Ioannis Kerenidis and Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. Sys. Sci., 69(3):395–420, 2004. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2004.04.007, arXiv:quant-ph/0208062]

[22]   Swastik Kopparty: List-decoding multiplicity codes. Theory of Computing, 11(5):149–182, 2015. [doi:10.4086/toc.2015.v011a005]

[23]   Swastik Kopparty, Shubhangi Saraf, and Sergey Yekhanin: High-rate codes with sublinear-time decoding. J. ACM, 61(5):28:1–28:20, 2014. Preliminary version in STOC’11. [doi:10.1145/2629416]

[24]   Peter D. Lax: Linear Algebra and Its Applications. Wiley, 2007.

[25]   Richard J. Lipton: Efficient checking of computations. In Proc. 7th Symp. Theoretical Aspects of Comp. Sci. (STACS’90), volume 415 of LNCS, pp. 207–215. Springer, 1990. [doi:10.1007/3-540-52282-4_44]

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

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

[28]   Adi Shamir: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90. [doi:10.1145/146585.146609]

[29]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. 6th Symp. Math. Found. Comput. Sci. (MFCS’77), volume 53 of LNCS, pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]

[30]   David P. Woodruff: New lower bounds for general locally decodable codes. Electron. Colloq. on Comput. Complexity (ECCC), 14(6), 2007. Available at ECCC.

[31]   David P. Woodruff: A quadratic lower bound for three-query linear locally decodable codes over any field. J. Comput. Sci. Techn., 27(4):678–686, 2012. Preliminary version in RANDOM’10. [doi:10.1007/s11390-012-1254-8]

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