Local List Decoding

Madhu Sudan
(Microsoft Research)

Two prominent themes in the modern era of algorithmic coding theory
are list-decoding of codes and local decoding of codes. Both of
these themes owe their origins to a single seminal work of Goldreich
and Levin, which gave a local list-decoding algorithm for the
Hadamard codes. This work was motivated by a cryptographic application,
that of constructing ``hardcore predicates for one-way functions''.
In this talk I will talk about the notion of local list-decodability,
its applications in cryptography and complexity theory, and some
of the early results in the area.