Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
List Decoding and Pseudorandom Constructions
verfasst von : Venkatesan Guruswami
Erschienen in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
There is a rich interplay between coding theory and computational complexity theory that has enriched both disciplines over the years. In particular, list decoding and closely related notions have been instrumental in several advances in explicit constructions of combinatorial objects with strong “random-like” properties, such as expander graphs, randomness extractors, and pseudorandom generators. Our aim here is to present
a unified list-decoding-centric view of the definition of these objects, and
the details of recent work due to the author, C. Umans, and S. Vadhan [3], where this viewpoint yields powerful results, namely the construction of unbalanced bipartite graphs with very strong expansion properties based on the list-decodable codes due to Parvaresh and Vardy [4]. In turn these expanders yield simple constructions of randomness extractors that are optimal up to constant factors.