[1]   Nir Ailon, Bernard Chazelle, Seshadhri Comandur, and Ding Liu: Property-preserving data reconstruction. Algorithmica, 51(2):160–182, 2008. Preliminary version in ISAAC’04. [doi:10.1007/s00453-007-9075-9]

[2]   Noga Alon and Joel H. Spencer: The Probabilistic Method. Wiley, 1992.

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

[4]   Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, and David P. Woodruff: Lower bounds for local monotonicity reconstruction from transitive-closure spanners. SIAM J. Discrete Math., 26(2):618–646, 2012. Preliminary version in RANDOM’10. [doi:10.1137/100808186]

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

[6]   Sourav Chakraborty, Eldar Fischer, and Arie Matsliah: Query complexity lower bounds for reconstruction of codes. In Proc. 2nd Symp. on Innovations in Computer Science (ICS’11), pp. 264–274, 2011. Accessible at ICS. See also ECCC.

[7]   Bernard Chazelle and C. Seshadhri: Online geometric reconstruction. J. ACM, 58(4):14, 2011. Preliminary version in SoCG’06. [doi:10.1145/1989727.1989728]

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

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

[10]   Paul Erds and Richard Rado: Intersection theorems for systems of sets. J. London Math. Soc., 35:85–90, 1960. Accessible at Alfréd Rényi Institute of Mathematics.

[11]   William I. Gasarch: A survey on private information retrieval (computational complexity column). Bulletin of the EATCS, 82:72–107, 2004. Accessible at Author’s Website.

[12]   Oded Goldreich, Shafi Goldwasser, and Dana Ron: Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998. Preliminary version in FOCS’96. [doi:10.1145/285055.285060]

[13]   Madhav Jha and Sofya Raskhodnikova: Testing and reconstruction of Lipschitz functions with applications to data privacy. SIAM J. Comput., 42(2):700–731, 2013. Preliminary version in FOCS’11. See also ECCC. [doi:10.1137/110840741]

[14]   Satyen Kale, Yuval Peres, and C. Seshadhri: Noise tolerance of expanders and sublinear expander reconstruction. SIAM J. Comput., 42(1):305–323. Preliminary version in FOCS’08. [doi:10.1137/110837863]

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

[16]   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 versions in STOC’03 and CoRR. [doi:10.1016/j.jcss.2004.04.007, arXiv:quant-ph/0208062]

[17]    Michael E. Saks and C. Seshadhri: Parallel monotonicity reconstruction. In Proc. 19th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’08), pp. 962–971. ACM Press, 2008. Accessible at ACM DL.

[18]   Luca Trevisan: Some applications of coding theory in computational complexity. Quaderni di Matematica, 13:347–424, 2004. See ECCC and CoRR. [arXiv:cs/0409044]

[19]   Stephanie Wehner and Ronald de Wolf: Improved lower bounds for locally decodable codes and private information retrieval. In Proc. 32th Internat. Colloq. on Automata, Languages and Programming (ICALP’05), pp. 1424–1436, 2005. [doi:10.1007/11523468_115, arXiv:quant-ph/0403140]

[20]   David P. Woodruff: New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(006), 2007. Accessible at ECCC.

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