Combinatorial construction of locally testable codes

ABSTRACT

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by Goldreich and Sudan (J. ACM 53(4)) and since then several Constructions of LTCs have been suggested.

While the best known construction of LTCs by Ben-Sasson and Sudan (STOC 2005) and Dinur (J. ACM 54(3)) achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. In this work we present a new and arguably simpler construction of LTCs that is purely combinatorial, does not rely on PCP machinery and matches the parameters of the best known construction. However, unlike the latter construction, our construction is not entirely explicit.

REFERENCES

• 1: N. Alon, J. Bruck, J. Naor, M. Naor, and R. Roth, Construction of asymptotically good low rate error-correcting codes through pseudo--random graphs, IEEE Transactions on Information Theory 38, 1992, pages 509--516.
• 2: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 3: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 4: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding, SIAM Journal on Computing, v.36 n.4, p.889-974, December 2006 [doi>10.1137/S0097539705446810]
• 5: E. Ben-Sasson and M. Sudan, Robust locally testable codes and products of codes, APPROX-RANDOM 2004, pages 286--297.
• 6: Eli Ben-Sasson , Madhu Sudan, Simple PCPs with poly-log rate and query complexity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060631]
• 7: D. Coppersmith and A. Rudra, On the robust testability of tensor products of codes, ECCC TR05--104, 2005.
• 8: Irit Dinur, The PCP theorem by gap amplification, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132553]
• 9: Irit Dinur , Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem, SIAM Journal on Computing, v.36 n.4, p.975-1024, December 2006 [doi>10.1137/S0097539705446962]
• 10: I. Dinur, M. Sudan and A. Wigderson, Robust local testability of tensor products of LDPC codes, APPROX-RANDOM 2006, pages 304--315.
• 11: L. Fortnow, J. Rompel and M. Sipser. On the power of multi--prover interactive protocols, In 3rd IEEE Symp. on Structure in Complexity Theory, 1988, pages 156--161. See errata in 5th IEEE Symp. on Structure in Complexity Theory, 1990, pages 318--319.
• 12: O. Goldreich, Short locally testable codes and proofs (Survey), ECCC TR05-014, 2005.
• 13: O. Goldreich and O. Meir, The tensor product of two good codes is not necessarily locally testable, ECCC TR07-062, 2007.
• 14: Oded Goldreich , Madhu Sudan, Locally testable codes and PCPs of almost-linear length, Journal of the ACM (JACM), v.53 n.4, p.558-655, July 2006 [doi>10.1145/1162349.1162351]
• 15: S. Hoory, N. Linial and A. Wigderson, Expander Graphs and their Applications, Bulletin of AMS, 43(4), 2006, pages 439--561.
• 16: Tali Kaufman , Madhu Sudan, Sparse Random Linear Codes are Locally Decodable and Testable, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.590-600, October 21-23, 2007 [doi>10.1109/FOCS.2007.65]
• 17: O. Meir, Combinatorial construction of locally testable codes, ECCC TR07-115.
• 18: Alexander Polishchuk , Daniel A. Spielman, Nearly-linear size holographic proofs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.194-203, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195132]
• 19: O. Reingold , S. Vadhan , A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.3, November 12-14, 2000
• 20: M. Sudan, Algorithmic introduction to coding theory, Lecture notes. Available from http://theory.csail.mit.edu/~madhu/FT01/, 2001.
• 21: P. Valiant, The tensor product of two codes is not necessarily robustly testable, APPROX-RANDOM 2005, pages 472--481.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.m MISCELLANEOUS

General Terms:
Theory

Keywords:
locally testable codes, pcps of proximity, probabilistically checkable proofs