UCSB CS Theory Colloquium Series

Spring 2022

Friday, March 4th, 2pm, Phelps 2510

Speaker: Venkatesan Guruswami (Berkeley/Simons)        

Title: Recent Progress on Binary Deletion-Correcting Codes
Abstract:
In the worst-case (bit)-deletion noise model, a subset of up to t arbitrarily chosen bits are deleted from a sequence of n codeword bits. Crucially, the locations of the deleted bits are not known to the receiver who receives a subsequence of the transmitted bit-string. The goal is to design codes of low redundancy that allow recovery of the deleted bits and the original codeword. The study of deletion-correcting codes itself is quite old, dating back to optimal single-deletion codes in the 1960s, and positive rate codes to correct t = Ω(n) deletions in the 1990s. However, many basic questions remained open and our understanding of deletion-correcting codes significantly lagged the vast literature concerning error-correcting codes to correct bit flips.

After a long hiatus, there has been much progress on deletion-correcting codes in the last 6-7 years, covering regimes when the number of deletions t is a small constant, a small constant fraction of n, and a large proportion of n, as well as the list-decoding model. The talk will survey some of this progress. The focus will be on binary codes for bit-deletions, but time permitting we might also briefly mention results for larger alphabets as well as the "insdel" model where symbols may be both inserted and deleted.

Bio:
Venkatesan Guruswami is currently a Professor of Computer Science at UC Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Until recently, he was a professor in the Computer Science Department at Carnegie Mellon University. Venkat received his Bachelor's degree from the Indian Institute of Technology, Madras, and his Ph.D. from MIT.
Venkat's research interests include coding theory, approximability of optimization problems, and computational complexity. He is the Editor-in-Chief of JACM, and was previously Editor-in-Chief of the ACM Transactions on Computation Theory and the president of the Computational Complexity Foundation. Venkat was a co-winner of the 2012 Presburger Award, and his other honors include a Simons Investigator award, Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and an IEEE Information Theory Society Paper Award. He is a fellow of the ACM and the IEEE.