List decoding algorithms for certain concatenated codes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

List decoding algorithms for certain concatenated codes

Full text

Pdf (1.10 MB)

Source

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

Portland, Oregon, United States

Pages: 181 - 190

Year of Publication: 2000

ISBN:1-58113-184-4

Authors

Venkatesan Guruswami	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA
Madhu Sudan	MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 42, Citation Count: 16

Additional Information:

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/335305.335327 What is a DOI?

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	Noga Alon, Packings with large minimum kissing numbers, Discrete Mathematics, v.175 n.1-3, p.249-251, Oct. 15, 1997 [doi>10.1016/S0012-365X(97)00071-X]
	2	N. ALON. Personal Communication, October 1999.
	3	N. ALON, J. BRUCK, J. NAOR, M. NAOR AND R. ROTH. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. on Information Theory, 38 (1992), pp. 509-516.
	4	P. DELSARTE. Bounds for unrestricted codes, by linear programming. Philips Res. Reports, 27 (1972), pp. 272-289.
	5	G. D. FORNEY. Generalized Minimum Distance Decoding. IEEE Trans. Inform. Theory, Vol. 12, pp. 125-131, 1966.
	6	Anna Gál , Shai Halevi , Erez Petrank , Richard Lipton, Computing From Partial Solutions, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.34, May 04-06, 1999
	7	h. GARCIA AND H. STICHTENOTH. A tower of Artin- Schreier extensions of function fields attaining the Drinfeld- Vladut bound. Inventiones Mathematicae, 121 (1995), pp. 211-222.
	8	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
	9	Venkatesan Guruswami , Madhu Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.28, November 08-11, 1998
	10	J. JUSTESEN. A class of constructive asymptotically good algebraic codes. IEEE Trans. Inform. Theory, 18 (1972), pp. 652-656.
	11	M. KIWI. Testing and weight distributions of dual codes. ECCC Technical Report TR-97-OI O, 1997.
	12	Ravi Kumar , D. Sivakumar, Proofs, Codes, and Polynomial-Time Reducibilities, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.46, May 04-06, 1999
	13	R. KOTTER AND A. VARDY. Algebraic soft-decoding of Reed-Solomon codes. Manuscript, August 1999.
	14	F. J. MACWILLIAMS AND N. J. A. SLOANE. The Theory of Error-Correcting Codes. Amsterdam: North Holland, 1977.
	15	Y. I. MANIN AND S. G. VLADUT. Linear codes and modular curves. J. Soviet. Math., 30 (1985), pp. 2611-2643.
	16	R. J. MCELIECE, E. R. RODEMICH, H. C. RUMSEY JR. AND L. R. WELCH. New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. on Inform. Theory, 23 (i 977), pp. 157-166.
	17	D. Sivakumar, On Membership Comparable Sets, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.2, June 15-18, 1998
	18	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]
	19	Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR Lemma (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.537-546, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301397]
	20	Y. SUGIYAMA, M. KASAHARA, S. HIRASAWA AND T. NAMEKAWA. A new class of asymptotically good codes beyond the Zyablov bound. IEEE Trans. Inform. Theory, 24 (1978), pp. 198-204.
	21	Y. SUGIYAMA, M. KASAHARA, $. HIRASAWA AND T. NAMEKAWA. Superimposed concatenated codes. IEEE Trans. Inform. Theory, 26 (1980), pp. 735-736.
	22	M. A. TSFASMAN, S. G. VL3.DUT AND T. ZINK. Modular curves, Shimura curves, and codes better than the Varshamov- Gilbert bound. Math. Nachrichten, 109:21-28, 1982.
	23	E. J. WELDON, JR. Justesen's construction - The low-rate case. IEEE Trans. Inform. Theory, 19 (1973), pp. 711-713.

CITED BY 16

	Venkatesan Guruswami , Piotr Indyk, Linear time encodable and list decodable codes, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Noga Alon , Venkatesan Guruswami , Tali Kaufman , Madhu Sudan, Guessing secrets efficiently via list decoding, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.254-262, January 06-08, 2002, San Francisco, California
	Lane A. Hemaspaandra, SIGACT news complexity theory column 38, ACM SIGACT News, v.33 n.4, December 2002
	Christopher Umans, Pseudo-random generators for all hardnesses, Journal of Computer and System Sciences, v.67 n.2, p.419-440, September 2003
	Christopher Umans, Pseudo-random generators for all hardnesses, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
	Elchanan Mossel , Christopher Umans, On the complexity of approximating the VC dimension, Journal of Computer and System Sciences, v.65 n.4, p.660-671, December 2002
	Venkatesan Guruswami, Limits to list decodability of linear codes, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Tran Van Trung , Sosina Martirosyan, New Constructions for IPP Codes, Designs, Codes and Cryptography, v.35 n.2, p.227-239, May 2005
	Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005
	Venkatesan Guruswami, Algorithmic results in list decoding, Foundations and Trends® in Theoretical Computer Science, v.2 n.2, p.107-195, January 2007
	Tomoyuki Yamakami, Quantum list decoding from quantumly corrupted codewords for classical block codes of polynomially small rate, Proceedings of the thirteenth Australasian symposium on Theory of computing, p.153-162, January 30-February 02, 2007, Ballarat, Victoria, Australia
	Adam Smith, Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.395-404, January 07-09, 2007, New Orleans, Louisiana
	Noga Alon , Venkatesan Guruswami , Tali Kaufman , Madhu Sudan, Guessing secrets efficiently via list decoding, ACM Transactions on Algorithms (TALG), v.3 n.4, p.42-es, November 2007
	Vitaly Feldman, On The Power of Membership Queries in Agnostic Learning, The Journal of Machine Learning Research, 10, p.163-182, June 2009