×

Robust locally testable codes and products of codes. (English) Zbl 1103.90080

Summary: We continue the investigation of locally testable codes, i.e., error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate that are testable with poly-logarithmically many queries. We note that these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes.

MSC:

94B60 Other types of codes
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
Full Text: DOI

References:

[1] , , , , Testing Reed–Muller codes, Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 2003), Lecture Notes in Computer Science, 2003, Vol. 2764, pp. 188–199.
[2] Probabilistic checking of proofs and the hardness of approximation problems, Ph.D. thesis, University of California at Berkeley, Berkeley, CA, 1994.
[3] Arora, J ACM 45 pp 501– (1998)
[4] Arora, J ACM 45 pp 70– (1998)
[5] , Improved low-degree testing and its applications, Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, Texas, 4–6 May 1997, pp. 485–495.
[6] , , , Checking computations in polylogarithmic time, Proceedings of the 23rd ACM Symposium on the Theory of Computing, ACM, New York, 1991, pp. 21–32.
[7] Babai, Comput Complex 1 pp 3– (1991)
[8] Bellare, IEEE Trans Inform Theory 42 pp 1781– (1996)
[9] , , , Efficient probabilistically checkable proofs and applications to approximation, Proceedings of the 25th ACM Symposium on the Theory of Computing, ACM, New York, 1993, pp. 294–304. · Zbl 1310.68083
[10] Babai, Combinator Probabil Comp 1 pp 1– (1992) · Zbl 0792.05064 · doi:10.1017/S0963548300000031
[11] , , , , Robust PCPs of proximity, shorter PCPs and applications to coding, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, 2004, pp. 1–10.
[12] , , Some 3-CNF properties are hard to test, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 345–354. · Zbl 1192.68347
[13] , , , Randomness efficient low-degree tests and short PCPs via -biased sets, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 612–621. · Zbl 1192.94089
[14] Blum, J Comp Syst Sci 47 pp 549– (1993)
[15] , Assignment-testers: Towards a combinatorial proof of the PCP-theorem, Proceedings of 45th IEEE Symposium on Foundations of Computer Science (FOCS 2004), Rome, Italy, 2004, pp. 155–164.
[16] Feige, J ACM 43 pp 268– (1996)
[17] , , Low-degree tests, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 1994, pp. 57–64.
[18] , Some improvements to total degree tests, Proceedings of the 3rd Annual Israel Symposium on Theory of Computing and Systems, Tel Aviv, Israel, 4–6 January 1995, pp. 190–198, Corrected version available online at http://theory.csail.mit.edu/madhu/papers/friedl.ps.
[19] Goldreich, SIAM J Comp 29 pp 1132– (1999)
[20] , Locally testable codes and PCPs of almost-linear length, Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, 16–19 November 2002.
[21] Random walks on graphs: A survey, Combinatorics, Paul Erdos is Eighty, , (Editors), Janos Bolyai Mathematical Society, Budapest, 2, 1996, pp. 353–398.
[22] , The Theory of Error-Correcting Codes, Elsevier/North-Holland, Amsterdam, 1981.
[23] , Nearly linear-size holographic proofs, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, Montreal, Quebec, Canada, 23–25 May 1994, pp. 194–203.
[24] , 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, ACM Press, 1997, pp. 475–484. · Zbl 0963.68175
[25] Rubinfeld, SIAM J Comp 25 pp 252– (1996)
[26] Algorithmic introduction to coding theory. Lecture notes, Available from http://theory.csail.mit.edu/madhu/FT01/, 2001.
[27] Tanner, IEEE Trans Inform Theory 27 pp 533– (1981)
[28] The tensor product of two codes is not necessarily robustly testable, Proceedings of 9th International Workshop on Randomization and Computation, UC Berkeley, August 2005. · Zbl 1142.94394
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.