List and local error-correction:

This talk will focus on coding against worst-case errors in two models that extend the classical requirement on the error-correction algorithm: list decoding and local decoding. In list decoding, the goal is to correct errors beyond the traditional half-the-minimum-distance limit, and the decoder is required to output a small list containing all codewords within the prescribed error bound. In local decoding, the goal is to recover any desired codeword (or information) symbol highly efficiently, by probing only a small portion of the noisy codeword. (One can also combine both notions and study local list decoding, and there are results in this vein with important complexity-theoretic ramifications; we will, however, not have a chance to discuss this.)

List decoding enables coding with information-theoretically optimal redundancy that is only epsilon higher than the worst-case error fraction, for any desired epsilon > 0. We will discuss work in algebraic coding theory that has led to explicit and efficiently decodable codes approaching this optimal trade-off between rate and error-correction radius. In particular, we will describe a simple linear-algebraic approach to list decode folded Reed-Solomon codes that achieves such a trade-off, and the idea of idea of pre-coding messages to “subspace-evasive sets” for optimizing the list size as well. The linear-algebraic method is quite versatile, and in combination with pre-coding via appropriate pseudorandom objects, extends to algebraic-geometric and rank metric codes as well.

For local error-correction, recent work has led to the construction of rate R, block length n codes that allow the recovery of any codeword symbol with n^{o(1)} queries even when the error-fraction approaches (1-R)/2 (which is the largest correctable error-fraction for unique decoding even without any locality restriction on the decoder). In the regime of a fixed number of queries, codes with sub-exponential length have been discovered for decoding information symbols by making as few as 3 queries to the noisy codeword. We will aim to state some of these results and the ideas used in the constructions.

BIO:

Venkatesan Guruswami received his Bachelor's degree in Computer Science from the Indian Institute of Technology at Madras in 1997 and his Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2001. He is currently a Professor in the Computer Science Department at Carnegie Mellon University. Earlier, during 2002-09, he was a faculty member at the University of Washington. Dr. Guruswami was a Miller Research Fellow at the UC Berkeley during 2001-02, and was a member in the School of Mathematics, Institute for Advanced Study during 2007-08.

Dr. Guruswami's research interests span several topics in theoretical computer science such as the theory of error-correcting codes, approximate optimization, constraint satisfaction, probabilistically checkable proofs, communication complexity and applications, and pseudorandomness.

Dr. Guruswami currently serves on the editorial boards of the Journal of the ACM, the SIAM Journal on Computing, and the ACM Transactions on Computation Theory, Previously, he was on editorial board of the IEEE Transactions on Information Theory. He was/is program committee chair for the 2012 IEEE Conference on Computational Complexity (CCC) and the 2015 IEEE Symposium on the Foundations of Computer Science (FOCS). He was an invited speaker at the 2010 International Congress of Mathematicians. Dr. Guruswami is a recipient of the Presburger Award (2012), Packard Fellowship (2005), Sloan Fellowship (2005), NSF CAREER award (2004), the ACM Doctoral Dissertation Award (2002), and the IEEE Information Theory Society Paper Award (2000).