Tensor Products of Weakly Smooth Codes are Robust

by Eli Ben-Sasson and Michael Viderman

Theory of Computing, Volume 5(12), pp. 239-255, 2009

Bibliography with links to cited articles

[1]   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. [STOC:10.1145/103418.103428].

[2]   Eli Ben-Sasson and Madhu Sudan: Robust locally testable codes and products of codes. In Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, and Dana Ron, editors, Proc. 8th Intern. Workshop on Randomization and Comput. (RANDOM’04), volume 3122 of LNCS, pp. 286–297. Springer, 2004. [doi:10.1007/b99805, ECCC:TR04-046].

[3]   Eli Ben-Sasson and Michael Viderman: Tensor products of weakly smooth codes are robust. In Ashish Goel, Klaus Jansen, José D. P. Rolim, and Ronitt Rubinfeld, editors, Proc. 12th Intern. Workshop on Randomization and Comput. (RANDOM’08), volume 5171 of LNCS, pp. 290–302. Springer, 2008. [doi:10.1007/978-3-540-85363-3_24].

[4]   Amir Bennatan and David Burshtein: On the application of LDPC codes to arbitrary discrete-memoryless channels. IEEE Trans. Inform. Theory, 50(3):417–438, 2004. [IEEE:10.1109/TIT.2004.824917].

[5]   Don Coppersmith and Atri Rudra: On the robust testability of product of codes. Technical Report 104, Elect. Colloq. Comput. Complex. (ECCC), 2005. [ECCC:TR05-104].

[6]   Irit Dinur, Madhu Sudan, and Avi Wigderson: Robust local testability of tensor products of LDPC codes. In Josep Díaz, Klaus Jansen, José D. P. Rolim, and Uri Zwick, editors, Proc. 10th Intern. Workshop on Randomization and Comput. (RANDOM’06), volume 4110 of LNCS, pp. 304–315. Springer, 2006. [doi:10.1007/11830924_29, ECCC:TR06-118].

[7]   R. G. Gallager: Low-density Parity Check Codes. MIT Press, 1963.

[8]   R. G. Gallager: Information Theory and Reliable Communication. Wiley, New York, 1968.

[9]   Oded Goldreich: Short locally testable codes and proofs (survey). Technical Report 014, Elect. Colloq. Comput. Complex. (ECCC), 2005. [ECCC:TR05-014].

[10]   Oded Goldreich and Or Meir: The tensor product of two good codes is not necessarily robustly testable. Technical Report 062, Elect. Colloq. Comput. Complex. (ECCC), 2007. [ECCC:TR07-062].

[11]   Oded Goldreich and Madhu Sudan: Locally testable codes and PCPs of almost-linear length. In Proc. 43rd FOCS, pp. 13–22. IEEE Comp. Soc. Press, 2002. [FOCS:10.1109/SFCS.2002.1181878, ECCC:TR02-050].

[12]   Grigoriĭ A. Margulis: Explicit constructions of graphs without short cycles and low density codes. Combinatorica, 2(1):71–78, 1982. [doi:10.1007/BF02579283].

[13]   Or Meir: Combinatorial construction of locally testable codes. In Richard E. Ladner and Cynthia Dwork, editors, Proc. 40th STOC, pp. 285–294. ACM Press, 2008. [STOC:1374376.1374419].

[14]   Michael Sipser and Daniel A. Spielman: Expander codes. IEEE Trans. Inform. Theory, 42(6):1710–1722, 1996. Preliminary version appeared in FOCS 1994. [IEEE:10.1109/18.556667].

[15]    Daniel A. Spielman: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6):1723–1731, 1996. Preliminary version appeared in STOC 1995. [IEEE:10.1109/18.556668].

[16]   Paul Valiant: The tensor product of two codes is not necessarily robustly testable. In Chandra Chekuri, Klaus Jansen, José D. P. Rolim, and Luca Trevisan, editors, Proc. 9th Intern. Workshop on Randomization and Comput. (RANDOM’05), volume 3624 of LNCS, pp. 472–481. Springer, 2005. [doi:10.1007/11538462_40].