List decoding tensor products and interleaved codes

ABSTRACT

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. (1) We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. (2) We show that for every code, its list decoding radius remains unchanged under m-wise interleaving for an integer m. This generalizes a recent result of Dinur.et.al, who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). (3)Using the notion of generalized Hamming weights, we give better list size bounds for both tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank-reduction together with other ideas, we obtain tight list size bounds for small fields.

Our results give better bounds on the list decoding radius than what is obtained from the Johnson bound, and yield rather general families of codes decodable beyond the Johnson bound.

REFERENCES

• 1: Eli Ben-Sasson , Madhu Sudan, Robust locally testable codes and products of codes, Random Structures & Algorithms, v.28 n.4, p.387-402, July 2006 [doi>10.1002/rsa.v28:4]
• 2: Daniel Bleichenbacher , Aggelos Kiayias , Moti Yung, Decoding interleaved Reed-Solomon codes over noisy channels, Theoretical Computer Science, v.379 n.3, p.348-360, July 2007 [doi>10.1016/j.tcs.2007.02.043]
• 3: D. Coppersmith and A. Rudra. On the robust testability of product of codes. Technical Report (104), ECCC, 2005.
• 4: Don Coppersmith , Madhu Sudan, Reconstructing curves in three (and higher) dimensional space from noisy data, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780563]
• 5: Irit Dinur , Elena Grigorescu , Swastik Kopparty , Madhu Sudan, Decodability of group homomorphisms beyond the johnson bound, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374418]
• 6: I. Dinur, M. Sudan, and A. Wigderson. Robust local testability of tensor products of LDPC codes. In APPROX-RANDOM'06, pages 304--315, 2006.
• 7: I. Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Info. Theory, pages 22--37, (2003).
• 8: P. Elias. Error-free coding. IEEE Trans. Info. Theory, 4(4):29--37, 1954.
• 9: P. Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT, 1957.
• 10: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 11: Parikshit Gopalan , Adam R. Klivans , David Zuckerman, List-decoding reed-muller codes over small fields, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374417]
• 12: V. Guruswami. List decoding from erasures: bounds and code constructions. IEEE Trans. Info. Theory, 49(11):2826--2833, 2003.
• 13: Venkatesan Guruswami, Better extractors for better codes?, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007422]
• 14: V. Guruswami. List Decoding of Error-Correcting Codes, volume 3282 of LNCS. Springer, 2004.
• 15: V. Guruswami. Algorithmic Results in List Decoding, volume 2 of FnT-TCS. Now Publishers, 2006.
• 16: V. Guruswami and A. Rudra. Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy. IEEE Trans. Info. Theory, 54(1):135--150, 2008.
• 17: V. Guruswami and M. Sudan. Improved decoding of Reed--Solomon and Algebraic-Geometric codes. IEEE Trans. Info. Theory, 45(6):1757--1767, 1999.
• 18: Subhash Khot, Hardness of approximating the shortest vector problem in lattices, Journal of the ACM (JACM), v.52 n.5, p.789-808, September 2005 [doi>10.1145/1089023.1089027]
• 19: Or Meir, Combinatorial construction of locally testable codes, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374419]
• 20: F. Parvaresh, M. El-Khamy, M. Stepanov, D. Augot, R. J. McEliece, and A. Vardy. Algebraic list decoding of Reed-Solomon product codes. In Proc. 10th Wkshp. on Algebraic and Combinatorial Coding Theory, pages 210--213, September 2006.
• 21: Farzad Parvaresh , Alexander Vardy, Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.285-294, October 23-25, 2005 [doi>10.1109/SFCS.2005.29]
• 22: R. Pellikaan and X.-W. Wu. List decoding of q-ary Reed-Muller codes. IEEE Trans. Info. Theory, 50(4):679--682, 2004.
• 23: S. Reddy and J. P. Robinson. Random error and burst correction by iterated code. IEEE Trans. Info. Theory, 18(1):182--185, 1972.
• 24: R.J.Serfling. Probability inequalities for the sum in sampling without replacement. Annals of Statistics, 2(1):39--48, (1974).
• 25: Madhu Sudan, Decoding of Reed Solomon codes beyond the error-correction bound, Journal of Complexity, v.13 n.1, p.180-193, March 1997 [doi>10.1006/jcom.1997.0439]
• 26: Madhu Sudan, List decoding: algorithms and applications, ACM SIGACT News, v.31 n.1, p.16-27, March 2000 [doi>10.1145/346048.346049]
• 27: A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Trans. Info. Theory, 50(12):3015--3025, 2004.
• 28: M. A. Tsfasman and S. G. Vluadut. Goemetric approach to higher weights. IEEE Trans. Info. Theory, 41:1564--1588, 1995.
• 29: P. Valiant. The tensor product of two codes is not necessarily robustly testable. In APPROX-RANDOM'05, pages 472--481, 2005.
• 30: J. Wozencraft. List decoding. Technical Report 48:90--95, Quarterly Progress Report, Research Laboratory of Electronics, MIT, 1958.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Error control codes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Johnson bound, generalized hamming weights, interleaved codes, linear transformations, list decoding, tensor products