Navigating the Deletion Channel

A deletion channel is communication medium that takes a string of symbols as input, deletes a fixed number of them and outputs the remaining symbols by aligning them without changing their order. Importantly, the position of the deleted symbol is not known at the output. A deletion-correcting code is a set of input strings with pairwise disjoint output sets. The central object of interest to us is the largest deletion correcting code for input strings of the same length. Despite many years of effort on this problem it remains open at a fundamental level.

A specific version of this problem, however, holds promise for a complete solution. For the case of binary strings and a single deletion, a number-theoretic construction is known, which partitions the 2^n binary strings of length n into n+1 classes, each of which is a single-deletion correcting code (called the Varshamov-Tenengolts codes). The largest of these classes is known to asymptotically optimal.

This seminar will discuss our recent efforts at solving this problem. We show that if suitably viewed the Varshamov-Tenengolts codes are simultaneously responsible for the solution of several combinatorial problems that appear to be otherwise unrelated. For the binary single-deletion case we find a new code construction that is asymptotically optimal. We obtain the first ever nonasymptotic upper bounds on sizes of the largest codes for arbitrary number of deletions and arbitrary alphabet size.

Remarkably, neither of our these results (or their proofs) show any number-theoretic character, despite the fact that the most promising code is number-theoretic. My aim in this seminar is to share these new results, speculate on possible connections and invite others to think on this problem.

Bio: Ankur is an Assistant Professor with the Systems and Control Engineering group at IIT Bombay and a recipient of the INSPIRE Faculty Award of the Department of Science and Technology, Government of India, 2013. He received his B.Tech. in Aerospace Engineering from IIT Bombay in 2006, M.S. in General Engineering in 2008 and Ph.D. in Industrial Engineering in 2010, both from the University of Illinois at Urbana-Champaign (UIUC). From 2010–2012 he was a post-doctoral researcher at the Coordinated Science Laboratory at UIUC. His research interests include game theory and economics, optimization and variational inequalities, combinatorial coding theory problems, the role of information in stochastic control, and operations research.