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.
Dr. Ankur Kulkarni got his B.Tech. in Aerospace Engg. from IIT Bombay and Ph.D. in Industrial and Systems Engg. from Uni. of Illinois at Urbana-Champaign. After a postdoctoral stint at UIUC, he joined the Interdisciplinary Programme in Systems and Control at IIT Bombay as Assistant Professor. His research interests are game theory, optimization, stochastic control, information and coding theory.