Sudan, Madhu List decoding: Algorithms and applications. (English) Zbl 1009.94572 van Leeuwen, Jan (ed.) et al., Theoretical computer science. Exploring new frontiers of theoretical informatics. International conference IFIP TCS 2000, Sendai, Japan, August 17-19, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1872, 25-41 (2000). Summary: Over the years coding theory and complexity theory have benefited from a number of mutually enriching connections. This article focuses on a new connection that has emerged between the two topics in the recent years. This connection is centered around the notion of list-decoding for error-correcting codes. In this survey we describe the list-decoding problem, the algorithms that have been developed, and a diverse collection of applications within complexity theory.For the entire collection see [Zbl 0944.00071]. Cited in 6 Documents MSC: 94B35 Decoding 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q25 Analysis of algorithms and problem complexity Keywords:list decoding; error-correcting codes; complexity theory PDFBibTeX XMLCite \textit{M. Sudan}, Lect. Notes Comput. Sci. 1872, 25--41 (2000; Zbl 1009.94572)