Better extractors for better codes?

ABSTRACT

We present an explicit construction of codes that can be list decoded from a fraction (1-ε) of errors in sub-exponential time and which have rate ε/log^O(1)(1/ε). This comes close to the optimal rate of Ω(ε), and is the first sub-exponential complexity construction to beat the rate of ε² achieved by Reed-Solomon or algebraic-geometric codes. Our construction is based on recent extractor constructions with very good seed length [17]. While the "standard" way of viewing extractors as codes (as in [16]) cannot beat the O(ε²) rate barrier due to the 2 log (1/ε) lower bound on seed length for extractors, we use such extractor codes as a component in a well-known expander-based construction scheme to get our result. The O(ε²) rate barrier also arises if one argues about list decoding using the minimum distance (via the so-called Johnson bound) --- so this also gives the first explicit construction that "beats the Johnson bound" for list decoding from errors.The main message from our work is perhaps conceptual, namely that good strong extractors for low min-entropies will yield near-optimal list decodable codes. Given all the progress that has been made on extractors, we view this as an optimistic avenue to look for better list decodable codes, both by looking for better explicit extractor constructions, as well as by importing non-trivial techniques from the extractor world in reasoning about and constructing codes.

REFERENCES

• 1: 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.
• 2: 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
• 3: Venkatesan Guruswami , Madhu Sudan, List decoding of error-correcting codes, 2001
• 4: Venkatesan Guruswami, Johan Hastad, Madhu Sudan, and David Zuckerman. Combinatorial Bounds for List Decoding. IEEE Transactions on Information Theory, 48(5):1021--1035, May 2002.
• 5: 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
• 6: 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]
• 7: Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
• 8: 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]
• 9: Jaikumar Radhakrishnan , Amnon Ta-Shma, Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators, SIAM Journal on Discrete Mathematics, v.13 n.1, p.2-24, Jan. 2000 [doi>10.1137/S0895480197329508]
• 10: Ronen Shaltiel. Recent Developments in Explicit Constructions of Extractors. Bulletin of the EATCS, 77:67--95, 2002.
• 11: C. Umans, Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.648, October 14-17, 2001
• 12: 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]
• 13: Madhu Sudan, List decoding: algorithms and applications, ACM SIGACT News, v.31 n.1, p.16-27, March 2000 [doi>10.1145/346048.346049]
• 14: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR lemma, Journal of Computer and System Sciences, v.62 n.2, p.236-266, March 2001 [doi>10.1006/jcss.2000.1730]
• 15: Aravind Srinivasan , David Zuckerman, Computing with Very Weak Random Sources, SIAM Journal on Computing, v.28 n.4, p.1433-1459, Aug. 1999 [doi>10.1137/S009753979630091X]
• 16: 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]
• 17: A. Ta-Shma , D. Zuckerman , S. Safra, Extractors from Reed-Muller Codes, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.638, October 14-17, 2001
• 18: Extractors and pseudorandom generators, Journal of the ACM (JACM), v.48 n.4, p.860-879, July 2001 [doi>10.1145/502090.502099]
• 19: Christopher Umans, Hardness of Approximating Minimization Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.465, October 17-18, 1999

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
error-correcting codes, expander graphs, list decoding, pseudorandomness, randomness extractors