Relaxed Locally Correctable Codes
by Tom Gur, Govind Ramnarayan, and Ron Rothblum
Theory of Computing, Volume 16(18), pp. 1-68, 2020
Bibliography with links to cited articles
[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.