Sampling codes with memory and the capacity of list-decoding from insertions

Prof. João Ribeiro

Abstract:

Informally, the capacity of list-decoding in a given adversarial error model is the largest rate at which we can list-decode with list size polynomial in the block length. The capacity of list-decoding from insertions and deletions is a basic, yet poorly understood, aspect of coding against synchronization errors. For example, when dealing with a fraction of insertions larger than 1/2, the best known lower bounds give little more than the fact that the capacity is positive. Beyond that regime we also only have loose bounds, with the lower bounds stemming from the analysis of uniformly random codes. In this talk I will discuss how sampling codes with memory allows us to determine the exact capacity of list-decoding binary codes from insertions, for all error rates. Based on joint work with Roni Con and Dean Doron.

Biography:

João Ribeiro is an assistant professor at Técnico-ULisboa and a researcher at Instituto de Telecomunicações. Previously, he was an assistant professor at Universidade Nova de Lisboa. Before that, João was a post doctoral fellow at Carnegie Mellon University, hosted jointly by Vipul Goyal and Venkatesan Guruswami, and a PhD student at Imperial College London, advised by Mahdi Cheraghchi. He was awarded an ERC Starting Grant in 2025.