Error-correcting codes play a crucial role in safeguarding data against the adverse effects of noise during communication and storage. They are also powerful tools that underlie several advances in theoretical computer science. The central challenge in coding theory is to construct codes with minimum possible redundancy for different noise models and requirements on the decoder, along with efficient algorithms for error-correction using those codes. Much progress has been made toward this quest, both in theory and practice, in the 65+ years since the birth of coding theory. Several fundamental problems, however, continue to challenge us, and exciting new questions have emerged to address the demands of modern technologies. This talk will survey some of our recent works on error-correction in various noise models, such as:
– worst-case errors, where we construct list decodable codes with redundancy as small as the target error fraction;
– i.i.d. errors, where we show polar codes enable efficient error-correction even as the redundancy approaches Shannon capacity;
– bit deletions, where we give the best known codes against both a constant number and a constant fraction of deletions;
– node failure in distributed storage, where we give low-bandwidth repair algorithms for the ubiquitous Reed-Solomon codes.
Venkatesan Guruswami, or Venkat, as his colleagues call him, received his Bachelor’s degree 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 was then a Miller Research Fellow at UC Berkeley during 2001-02. Venkat is currently a Professor in the Computer Science Department at Carnegie Mellon University. Venkat was on the faculty at University of Washington during 2002-07, and has held visiting positions at the Institute for Advanced Study, Princeton (2007-08) and Microsoft Research New England (2014).
Venkat’s research interests span several topics in theoretical computer science including coding theory, complexity of approximate optimization and constraint satisfaction, pseudorandomness, and communication complexity. Venkat currently serves on the editorial boards of the Journal of the ACM, SIAM Journal on Computing, and Research in the Mathematical Sciences; he was previously an associate editor for the IEEE Transactions on Information Theory and ACM Transactions on Computation Theory. Venkat served as the program committee chair for the 2015 IEEE Symposium on Foundations of Computer Science (FOCS) and 2012 IEEE Conference on Computational Complexity (CCC). He was an invited speaker at the 2010 International Congress of Mathematicians. Venkat is a recipient of the EATCS Presburger Award, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and the IEEE Information Theory Society Paper Award.
