Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. (English) Zbl 1192.94132
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 812-821, electronic only (2002).
MSC:
| 94B35 | Decoding |
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.]] · Zbl 0744.94023 |
| [2] | Noga Alon, Jeff Edmonds and Michael Luby. Linear time erasure codes with nearly optimal recovery. Proceedings of FOCS’95.]] |
| [3] | Alexander Barg and Gillés Zémor. Error exponents of expander codes. IEEE Transactions on Information Theory, to appear, 2001.]] |
| [4] | E. L. Blokh and V. V. Zyablov. Linear concatenated codes. Nauka, Moscow, 1982 (in Russian).]] |
| [5] | Ilya I. Dumer. Concatenated codes and their multilevel generalizations. In V. S. Pless and W. C. Huffman, editors, Handbook of Coding Theory, volume 2, pages 1911-1988. North Holland, 1998.]] · Zbl 0967.94029 |
| [6] | G. David Forney. Generalized Minimum Distance decoding. IEEE Transactions on Information Theory, 12:125-131, 1966.]] · Zbl 0253.94007 |
| [7] | Venkatesan Guruswami. List Decoding of Error-Correcting Codes. Ph.D thesis, Massachusetts Institute of Technology, August 2001.]] |
| [8] | Venkatesan Guruswami. List decoding from erasures: Bounds and code constructions. Proceedings of the 21st Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, pages 195-206, December 2001.]] · Zbl 1052.94505 |
| [9] | Venkatesan Guruswami and Piotr Indyk. Expander-based constructions of efficiently decodable codes. Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, Las Vegas, NV, pages 658-667, October 2001.]] |
| [10] | Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757-1767, 1999.]] · Zbl 0958.94036 |
| [11] | Piotr Indyk. List decoding in linear-time. Manuscript, 2002.]] |
| [12] | G. L. Katsman, Michael A. Tsfasman, and Serge G. Vlǎdut. Modular curves and codes with a polynomial construction. IEEE Transactions on Information Theory, 30:353-355, 1984.]] · Zbl 0544.94016 |
| [13] | Alex Lubotzky, R. Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.]] · Zbl 0661.05035 |
| [14] | Rasmus R. Nielsen and Tom Høholdt. Decoding Reed-Solomon codes beyond half the minimum distance. Coding Theory, Cryptography and Related areas, (eds. Buchmann, Hoeholdt, Stichtenoth and H. tapia-Recillas), pages 221-236, 1999.]] |
| [15] | 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.]] · Zbl 1001.94046 |
| [16] | Ba-Zhong Shen. A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate. IEEE Transactions on Information Theory, 39:239-242, 1993.]] · Zbl 0766.94022 |
| [17] | M. Amin Shokrollahi and Hal Wasserman. List decoding of algebraic-geometric codes. IEEE Transactions on Information Theory, 45(2):432-437, 1999.]] · Zbl 0947.94024 |
| [18] | Michael Sipser and Daniel Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996.]] · Zbl 0943.94543 |
| [19] | Daniel Spielman. Computationally Efficient Error-Correcting Codes and Holographic Proofs. Ph.D thesis, Massachusetts Institute of Technology, June 1995.]] |
| [20] | Daniel Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723-1732, 1996.]] · Zbl 0943.94544 |
| [21] | Madhu Sudan. Decoding of Reed-Solomon codes beyond the error-correction bound. Journal of Complexity, 13(1):180-193, 1997.]] 10.1006/jcom.1997.0439 · Zbl 0872.68026 |
| [22] | Gillés Zémor. On expander codes. IEEE Transactions on Information Theory, 47(2):835-837, 2001.]] · Zbl 1021.94025 |
| [23] | Victor V. Zyablov. An estimate of the complexity of constructing binary linear cascaded codes. Problemy Peridachi Informatsii, 15(2):58-70, 1971.]] |
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.
