Serge Kas Hanna
Title: Guess & Check Codes for Deletions, Insertions, and Synchronization
Abstract: We consider the problem of constructing binary codes that can correct multiple deletions. Varshamov-Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion correcting codes, and have an asymptotically optimal redundancy. Finding similar codes for more than one deletion remains an open problem. In our work, we make progress by relaxing the standard zero-error decoding requirement. To this end, we assume that the input message is uniform iid and that the positions of the deletions are independent of the codeword. Our contribution is a new family of systematic codes, that we call Guess & Check (GC) codes, that can with high probability correct multiple deletions (or insertions). GC codes have logarithmic redundancy; and deterministic polynomial time encoding and decoding algorithms.
In this talk, I will discuss the construction of GC codes and present the theoretical results on the properties of these codes, i.e., redundancy, complexity, and probability of successful decoding. I will also present numerical simulations which include results on the application of GC codes to file synchronization. I will also briefly discuss extensions of GC codes to correcting localized (bursty) deletions; and to list decoding.
Biography: Serge Kas Hanna is a third year Ph.D. student at Rutgers University, working with Prof. Salim El Rouayheb. He received a Diploma in computer and communications engineering from the Lebanese University, Faculty of Engineering, in 2015. He also received a M.S. degree in computer and information systems engineering from the Lebanese University, Doctoral school, in 2015. His research interests are in the broad area of information theory and coding theory with a focus on coding for synchronization.