×

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].

MSC:

94B35 Decoding
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite