TOPIC Recent Progress on Binary Codes for Worst-Case Deletions 
AREA Communications & Networks  
SPEAKER Venkatesan Guruswami (Professor of Computer Science, Carnegie Mellon University) 
DATE 29 September 2016, Thursday 
TIME 11.00am to 12.00pm 
VENUE E4-04-06, ECE Seminar Room, Engineering Block E4, NUS 
FEES No Charge 

This talk will discuss some recent progress on code constructions for recovery from worst-case bit deletions.

The first part will consider the case of a large fraction of deletions, where we construct a family of binary codes of positive rate to recover from a fraction 0.414 of deletions. Previously, even non- constructively the largest deletion fraction known to be correctable with positive rate was around 0.17. For alphabet size k, we are able to correct a deletion fraction exceeding (k-1)/(k+1), with (k-1)/k being a trivial upper limit. Whether a deletion fraction approaching 1/2 is correctable by binary codes remains a tantalizing open question. (Joint work with Boris Bukh and Johan Hastad.)

The second part will consider the other noise regime, of correcting from a small fixed number k of deletions. The single deletion case is well understood since 1965, and an asymptotically optimal explicit construction with ~ 2^n/n codewords of length n, i.e., at most log n bits of redundancy, is known. However, even for the case of two deletions, there was no known explicit construction with redundancy less than n^{Omega(1)}. For any fixed k, we construct binary codes with O(k^2 log k log n) redundancy for efficient recovery from k deletions. The optimal, non-constructive bound is Theta(k log n) bits of redundancy. (Joint work with Joshua Brakensiek and Samuel Zbarksy.) 

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 many 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. 

Host: Dr TAN Yan Fu, Vincent 

 | Back to seminar list |

All are welcome to attend these seminars.
Should you have any enquiries, please contact Ms Veronica Au , Tel: 6516 2109.