Linear time encodable and list decodable codes

ABSTRACT

We present the first construction of error-correcting codes which can be (list) decoded from a noise fraction arbitrarily close to 1 in linear time. Specifically, we present an explicit construction of codes which can be encoded in linear time as well as list decoded in linear time from a fraction (1-ε) of errors for arbitrary ε > 0. The rate and alphabet size of the construction are constants that depend only on ε. Our construction involves devising a new combinatorial approach to list decoding, in contrast to all previous approaches which relied on the power of decoding algorithms for algebraic codes like Reed-Solomon codes.Our result implies that it is possible to have, and in fact explicitly specifies, a coding scheme for arbitrarily large noise thresholds with only constant redundancy in the encoding and constant amount of work (at both the sending and receiving ends) for each bit of information to be communicated. Such a result was known for certain probabilistic error models, and here we show that this is possible under the stronger adversarial noise model as well.

REFERENCES

• 1: Michael Alekhnovich, Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.439-448, November 16-19, 2002
• 2: Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ronny Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38:509--516, 1992.
• 3: N. Alon , F. R. K. Chung, Explicit construction of linear sized tolerant networks, Discrete Mathematics, v.72 n.1-3, p.15-19, December 1988 [doi>10.1016/0012-365X(88)90189-6]
• 4: N. Alon , J. Edmonds , M. Luby, Linear time erasure codes with nearly optimal recovery, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.512, October 23-25, 1995
• 5: Sigal Ar , Richard J. Lipton , Ronitt Rubinfeld , Madhu Sudan, Reconstructing Algebraic Functions from Mixed Data, SIAM Journal on Computing, v.28 n.2, p.487-510, April 1999 [doi>10.1137/S0097539796297577]
• 6: Daniel Bleichenbacher and P. Nguyen, Noisy Polynomial Interpolation and Noisy Chinese Remaindering. Proceedings of EUROCRYPT '2000, LNCS vol. 1807, Springer-Verlag, pp. 53--69, 2000.
• 7: Peter Elias. List decoding for noisy channels. Wescon Convention Record, Part 2, Institute of Radio Engineers (now IEEE), pp. 94--104, 1957.
• 8: G. L. Feng. Two Fast Algorithms in the Sudan Decoding Procedure. Proceedings of the 37th Annual Allerton Conference on Communication, Control and Computing, pp. 545--554, 1999.
• 9: Venkatesan Guruswami , Madhu Sudan, List decoding of error-correcting codes, 2001
• 10: V. Guruswami , P. Indyk, Expander-Based Constructions of Efficiently Decodable Codes, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.658, October 14-17, 2001
• 11: Venkatesan Guruswami , Piotr Indyk, Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510023]
• 12: Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 13: Venkatesan Guruswami , Madhu Sudan, List decoding algorithms for certain concatenated codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.181-190, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335327]
• 14: J. Kuczynski , H. Wozniakowski, Probabilistic Bounds on the Extremal Eigenvalues and Condition Number by the Lanczos Algorithm, SIAM Journal on Matrix Analysis and Applications, v.15 n.2, p.672-691, April 1994 [doi>10.1137/S0895479892230456]
• 15: Alex Lubotzky, R. Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261--277, 1988.
• 16: Ronny Roth and Gitit Ruckenstein. Efficient decoding of Reed-Solomon codes beyond half the minimum distance. IEEE Transactions on Information Theory, 46(1):246--257, January 2000.
• 17: Daniel Alan Spielman , Michael Sipser, Computationally efficient error-correcting codes and holographic proofs, 1995
• 18: Daniel Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723--1732, 1996.
• 19: Daniel A. Spielman, The Complexity of Error-Correcting Codes, Proceedings of the 11th International Symposium on Fundamentals of Computation Theory, p.67-84, September 01-03, 1997
• 20: 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]
• 21: Amnon Ta-Shma , David Zucherman, Extractor codes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.193-199, July 2001, Hersonissos, Greece [doi>10.1145/380752.380800]
• 22: J. M. Wozencraft. List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT, Vol. 48 (1958), pp. 90--95.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
adversarial noise model, expander graphs, linear time computation, list decoding, spectral partitioning