Title: 
List decoding of binary codes: Improved results via new concatenation schemes

Speaker: Venkat Guruswami, IAS and U. Washington

Abstract:
Recent progress in algebraic coding theory has led to the construction of 
error-correcting codes with the optimal trade-off between information rate 
and the fraction of worst-case errors corrected (in the model of list 
decoding). These codes, which are folded versions of the classical 
Reed-Solomon codes, are defined over large alphabets. The corresponding 
program of achieving list decoding capacity for binary codes -- namely 
constructing binary codes of rate approaching 1-H(p) to list decode a 
fraction p of errors -- remains a major long term challenge.

In this talk, I will discuss the following three results on list decoding of 
binary codes. All of them use a concatenation scheme with an outer folded 
Reed-Solomon code, and crucially rely on the powerful list decoding property 
of these codes.

   1. Polynomial-time constructible binary codes with the currently best known
trade-off between error-correction radius and rate, achieving the so-called 
Blokh-Zyablov bound.
   2. Existence of binary concatenated codes that achieve list decoding 
capacity, which is encouraging given the preeminent role played by code 
concatenation in constructing good binary codes.
   3. Explicit binary codes for correcting a fraction (1/2-eps) of errors for 
eps -> 0 with block length growing as 1/eps^3; improving this cubic 
dependence will likely require a substantially new approach.


Based on joint works with Atri Rudra appearing in RANDOM'07, SODA'08, and 
CCC'08.