Locally testable codes and PCPs of almost-linear length

ABSTRACT

We initiate a systematic study of locally testable codes; that is, error-correcting codes that admit very efficient membership tests. Specifically, these are codes accompanied with tests that make a constant number of (random) queries into any given word and reject non-codewords with probability proportional to their distance from the code.Locally testable codes are believed to be the combinatorial core of PCPs. However, the relation is less immediate than commonly believed. Nevertheless, we show that certain PCP systems can be modified to yield locally testable codes. On the other hand, we adapt techniques that we develop for the construction of the latter to yield new PCPs.Our main results are locally testable codes and PCPs of almost-linear length. Specifically, we prove the existence of the following constructs:---Locally testable binary (linear) codes in which k information bits are encoded by a codeword of length k ⋅ exp(Õ(√(log k))). This improves over previous results that either yield codewords of exponential length or obtained almost quadratic length codewords for sufficiently large nonbinary alphabet.---PCP systems of almost-linear length for SAT. The length of the proof is n ⋅ exp(Õ(√(log n))) and verification in performed by a constant number (i.e., 19) of queries, as opposed to previous results that used proof length n^{(1 + O(1/q))} for verification by q queries.The novel techniques in use include a random projection of certain codewords and PCP-oracles that preserves local-testability, an adaptation of PCP constructions to obtain “linear PCP-oracles” for proving conjunctions of linear conditions, and design of PCPs with some new soundness properties---a direct construction of locally testable (linear) codes of subexponential length.

REFERENCES

• 1: Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., and Ron, D. 2003. Testing low-degree polynomials over GF(2). In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2003). Lecture Notes in Computer Science, vol. 2754, Springer, New York, 188--199.
• 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: Arora, S., and Sudan, M. 2003. Improved low degree testing and its applications. Combinatorica 23, 3, 365--426.
• 5: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 6: Babai, L., Fortnow, L., and Lund. C. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 13--40.
• 7: Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M., and Sudan, M. 1996. Linearity testing over characteristic two. IEEE Trans. Info. Theory 42, 6 (Nov.), 1781--1795.
• 8: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 9: M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
• 10: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007361]
• 11: Ben-Sasson, E., Goldreich, O., and Sudan, M. 2003a. Bounds on 2-query codeword testing. In Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2003). Lecture Notes in Computer Science, Vol. 2764. Springer, New York, 216--227.
• 12: 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]
• 13: Eli Ben-Sasson , Madhu Sudan , Salil Vadhan , Avi Wigderson, Randomness-efficient low degree tests and short PCPs via epsilon-biased sets, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780631]
• 14: Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
• 15: Nadia Creignou , Sanjeev Khanna , Madhu Sudan, Complexity classifications of boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 16: 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]
• 17: Irit Dinur , Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.155-164, October 17-19, 2004 [doi>10.1109/FOCS.2004.16]
• 18: Shimon Even , Alan L. Selman , Yacov Yacobi, The complexity of promise problems with applications to public-key cryptography, Information and Control, v.61 n.2, p.159-173, May 1984 [doi>10.1016/S0019-9958(84)80056-X]
• 19: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 20: Forney, Jr., G. D. 1966. Concatenated Codes. MIT Press, Cambridge, MA.
• 21: Some improvements to total degree tests, Proceedings of the 3rd Israel Symposium on the Theory of Computing Systems (ISTCS'95), p.190, January 04-06, 1995
• 22: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 23: Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.175, May 21-24, 2002
• 24: Goldreich, O., and Sudan, M. 2002. Locally testable codes and PCPs of almost-linear length tech. Rep. TR02-050, ECCC.
• 25: Harsha, P., and Sudan. M. 2000. Small PCPs with low query complexity. Computat. Complex. 9, (3--4), 157--201.
• 26: Håstad, J. 1999. Clique is hard to approximate within n^{1 − ε}. Acta Math. 182, 105--142.
• 27: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 28: Kiwi, M. 2003. Algebraic testing and weight distribution of dual codes. TR97-010.
• 29: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 30: 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]
• 31: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 32: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Algorithms, Theory, Verification

Keywords:
Proof verification, derandomization, error-correcting codes, probabilistically checkable proofs