[1]   Noga Alon and Yuval Roichman: Random Cayley graphs and expanders. Random Struct. Algorithms, 5(2):271–284, 1994. [doi:10.1002/rsa.3240050203]

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

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

[6]   Jop Briët: On embeddings of ℓ₁^k from locally decodable codes, 2016. [arXiv:1611.06385]

[7]   Jop Briët, Zeev Dvir, and Sivakanth Gopi: Outlaw distributions and locally decodable codes. In Proc. 8th Symp. Innovations in Theoret. Comp. Sci. (ITCS’17), pp. 20:1–20:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.20, arXiv:1609.06355]

[8]   Jop Briët and Sivakanth Gopi: Gaussian width bounds with applications to arithmetic progressions in random settings. Internat. Math. Res. Notices, 2018. [doi:10.1093/imrn/rny238, arXiv:1711.05624]

[9]   Jop Briët, Assaf Naor, and Oded Regev: Locally decodable codes and the failure of cotype for projective tensor products. Electron. Res. Announc. Math. Sci., 19:120–130, 2012. [doi:10.3934/era.2012.19.120, arXiv:1208.0539]

[10]   Jop Briët and Shravas Rao: Arithmetic expanders and deviation bounds for random tensors, 2016. [arXiv:1610.03428]

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

[12]   Gil Cohen and Avishay Tal: Two structural results for low degree polynomials and applications. In Proc. Internat. Workshop on Approximation, Randomization, and Combinat. Optim. (RANDOM’15), pp. 680–709. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.680, arXiv:1404.0654]

[13]   David Conlon and Yufei Zhao: Quasirandom Cayley graphs. Discrete Analysis, pp. 6:1–6:14, 2017. [doi:10.19086/da.1294, arXiv:1603.03025]

[14]   Zeev Dvir: On the size of Kakeya sets in finite fields. J. Amer. Math. Soc., 22(4):1093–1097, 2009. [doi:10.1090/S0894-0347-08-00607-3, arXiv:0803.2336]

[15]   Zeev Dvir and Sivakanth Gopi: 2-Server PIR with subpolynomial communication. J. ACM, 63(4):39:1–39:15, 2016. Preliminary version in STOC’15. [doi:10.1145/2968443, arXiv:1407.6692]

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

[17]   Nikos Frantzikinakis, Emmanuel Lesigne, and Máté Wierdl: Random sequences and pointwise convergence of multiple ergodic averages. Indiana Univ. Math. J., 61(2):585–617, 2012. [doi:10.1512/iumj.2012.61.4571]

[18]   Nikos Frantzikinakis, Emmanuel Lesigne, and Máté Wierdl: Random differences in Szemerédi’s theorem and related results. J. d’Analyse Mathématique, 130(1):91–133, 2016. [doi:10.1007/s11854-016-0030-z, arXiv:1307.1922]

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

[20]   Oded Goldreich, Howard 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]

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

[22]   Sivakanth Gopi, Swastik Kopparty, Rafael Oliveira, Noga Ron-Zewi, and Shubhangi Saraf: Locally testable and locally correctable codes approaching the Gilbert-Varshamov bound. IEEE Trans. Inform. Theory, 64(8):5813–5831, 2018. Preliminary version in SODA’17. [doi:10.1109/TIT.2018.2809788]

[23]    Ben Green and Tom Sanders: Boolean functions with small spectral norm. Geom. Funct. Anal., 18(1):144–162, 2008. [doi:10.1007/s00039-008-0654-y, arXiv:math/0605524]

[24]   Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]

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

[26]   Tali Kaufman and Madhu Sudan: Sparse random linear codes are locally decodable and testable. In Proc. 48th FOCS, pp. 590–600. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.8]

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

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

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

[30]   Zeph Landau and Alexander Russell: Random Cayley graphs are expanders: A simple proof of the Alon–Roichman theorem. Electron. J. Combin., 11(1):R62, 2004.

[31]   Shahar Mendelson and Roman Vershynin: Entropy and the combinatorial dimension. Inventiones Math., 152(1):37–55, 2003. [doi:10.1007/s00222-002-0266-3, arXiv:math/0203275]

[32]   Claude E. Shannon: A mathematical theory of communication. Bell System Tech. J., 27(3):379–423, 623–656, 1948. [doi:10.1002/j.1538-7305.1948.tb01338.x]

[33]   Amir Shpilka, Avishay Tal, and Ben Lee Volk: On the structure of Boolean functions with small spectral norm. Comput. Complexity, 26(1):229–273, 2017. Preliminary version in ITCS’14. [doi:10.1007/s00037-015-0110-y, arXiv:1304.0371]

[34]   Michel Talagrand: Upper and Lower bounds For Stochastic Processes. Springer, 2014. [doi:10.1007/978-3-642-54075-2]

[35]   Terence Tao: Higher Order Fourier Analysis. Amer. Math. Soc., 2012. [doi:10.1090/gsm/142]

[36]   Terence Tao: Algebraic combinatorial geometry: The polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory. EMS Surveys in Math. Sciences, 1(1):1–46, 2014. [doi:10.4171/EMSS/1, arXiv:1310.6482]

[37]   Terence Tao and Van Vu: Additive Combinatorics. Cambridge Univ. Press, 2006. [doi:10.1017/CBO9780511755149]

[38]   David Woodruff: New lower bounds for general locally decodable codes. Electronic Colloq. Comput. Complexity (ECCC’07), 14(6), 2007.

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

[40]   Sergey Yekhanin: Locally decodable codes. Found. Trends Theor. Comput. Sci., 6(3):139–255, 2012. Preliminary version in CSR’11. [doi:10.1561/0400000030]