Venkatesan Guruswami

Abstract:   A fundamental trade-off in coding theory is the one between the proportion of redundancy built into codewords and the fraction of errors that can be corrected. In this talk, I will describe an explicit construction of codes that achieves the optimal trade-off between these parameters. Formally, for every 0 < p < 1 and eps > 0, we (joint work with A. Rudra) present an explicit construction of codes with redundancy (p+eps) (i.e., which encode (1-p-eps)n information symbols into n codeword symbols) that can be list decoded in polynomial time from up to a fraction p of errors. For low noise levels (small p), this gives almost a factor 2 improvement over the best previous result. We stress that our result holds in a worst-case noise model where the channel can corrupt the codeword arbitrarily subject to the bound p on the proportion of errors. Our codes are simple to describe: they are certain "folded" Reed-Solomon (RS) codes, which are obtained from the classical RS codes via a careful bundling of codeword symbols. A central algebraic idea used in our work is that certain automorphisms of rational function fields induce a low-degree map on polynomials of bounded degree (when these are viewed as elements of a suitable extension field). Discovering a similar phenomenon over more general function fields, with the space of sections of some bounded-degree divisor replacing polynomials, could lead to exciting new algebraic codes. The talk will introduce the problem of list decoding, and then give a peek into the algebraic ideas underlying the above result. I will also briefly describe some recent work (joint with C. Umans and S. Vadhan) on how ideas behind folded RS codes and their precursor, the Parvaresh-Vardy codes, yield a new, simple construction of unbalanced bipartite expander graphs with expansion close to the degree.