Limits to list decodability of linear codes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Limits to list decodability of linear codes

Full text

Pdf (243 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 12B table of contents

Pages: 802 - 811

Year of Publication: 2002

ISBN:1-58113-495-9

Author

Venkatesan Guruswami

University of California at Berkeley, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 25, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.510022 What is a DOI?

ABSTRACT

We consider the problem of the best possible relation between the list decodability of a binary linear code and its minimum distance. We prove, under a widely-believed number-theoretic conjecture, that the classical "Johnson bound" gives, in general, the best possible relation between the list decoding radius of a code and its minimum distance. The analogous result is known to hold by a folklore random coding argument for the case of non-linear codes, but the linear case is more subtle and has remained open.We prove our result by exhibiting an infinite family of binary linear codes of "large" minimum distance with a super-polynomial number (in blocklength) of codewords all within a Hamming ball of radius close to the Johnson bound. Even the existence of codes with a super-polynomial number of codewords in a ball of radius bounded away from the minimum distance (let alone radius close to the Johnson bound) was open prior to our work. We also unconditionally prove the "tightness" of the Johnson bound for decoding with list size that is an arbitrarily large constant.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Emil Artin. Collected Papers. ed. S. Lang and J. T. Tate, Springer-Verlag, 1965. pp. viii--ix.
	2	Peter Elias. List decoding for noisy channels. Technical Report 335, Research Laboratory of Electronics, MIT, 1957.
	3	Peter Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory, 37:5--12, 1991.
	4	O. Goldreich , R. Rubinfeld , M. Sudan, Learning polynomials with queries: The highly noisy case, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.294, October 23-25, 1995
	5	Venkatesan Guruswami , Madhu Sudan, List decoding of error-correcting codes, 2001
	6	Venkatesan Guruswami, Johan Håstad, Madhu Sudan, and David Zuckerman. Combinatorial bounds for list decoding. Proceedings of the 38th Annual Allerton Conference on Communication, Control and Computing, pages 603--612, October 2000.
	7	V. Guruswami , A. Sahai , M. Sudan, "Soft-decision" decoding of Chinese remainder codes, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.159, November 12-14, 2000
	8	Venkatesan Guruswami and Madhu Sudan. Improved decoding of Reed-Solomon and algebraic-geometric codes. IEEE Transactions on Information Theory, 45:1757--1767, 1999.
	9	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]
	10	Venkatesan Guruswami and Madhu Sudan. Extensions to the Johnson bound. Manuscript, February 2001. The results also appear in {5, Chapter 3}.
	11	Christopher Hooley. On Artin's conjecture. J. Reine Angew. (MATH)., 225:209--220, 1967.
	12	Selmer M. Johnson. A new upper bound for error-correcting codes. IEEE Transactions on Information Theory, 8:203--207, 1962.
	13	Jørn Justesen and Tom Høholdt. Bounds on list decoding of MDS codes. IEEE Transactions on Information Theory, 47(4):1604--1609, May 2001.
	14	Ralf Koetter and Alexander Vardy. Algebraic soft-decision decoding of Reed-Solomon codes. Proceedings of the 38th Annual Allerton Conference on Communication, Control and Computing, pages 625--635, October 2000.
	15	F. J. MacWilliams and Neil J. A. Sloane. The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam, 1981.
	16	M. Ram Murty. Artin's conjecture for primitive roots. (MATH). Intelligencer, 10(4):59-67, 1988.
	17	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]
	18	John M. Wozencraft. List Decoding. Quarterly Progress Report, Research Laboratory of Electronics, MIT, 48:90--95, 1958.

CITED BY 3

	Venkatesan Guruswami , Igor Shparlinski, Unconditional proof of tightness of Johnson bound, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Venkatesan Guruswami , Atri Rudra, Explicit capacity-achieving list-decodable codes, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Venkatesan Guruswami, Algorithmic results in list decoding, Foundations and Trends® in Theoretical Computer Science, v.2 n.2, p.107-195, January 2007