The paper, entitled ‘Efficient and rate-optimal list-decoding in the presence of minimal feedback: Weldon and Slepian-Wolf in sheep's clothing’ will be presented at this prestigious conference, sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in New York.
In coding theory and information theory, i.e. the mathematics of communication, a central object of interest is "list-decodable codes". These are collections of sequences such that for an arbitrary other sequence, there is only a small list of members from the collection that are close to it. Such objects are useful for error-correction, cryptography, and robust algorithm design. It is a long-standing problem to construct such codes with fast decoding algorithms that find a small list for any given sequence. This paper, led by Bristol Maths Undergraduate alumnus (and summer bursary student) Daniel McMorrow (currently pursuing a Ph.D. at the National University of Singapore) and international Bristol Maths summer research intern Pranav Joshi (currently pursuing a Ph.D. at the California Institute of Technology), and co-authored by two Bristol Maths faculty members Yihan Zhang and Sidharth Jaggi along with colleague Amitalok J. Budkuley from IIT Kharagpur, made substantial progress on this question. Specifically, the authors brought deep insights from information theory to show that such a desired efficient decoding scheme is possible at the cost of allowing a tiny amount of feedback from the decoder.
This project started in 2021 with Pranav Joshi being the driving force towards understanding the power of feedback in efficient communication. This led to a partial result, which can be accessed online. Daniel McMorrow joined the team in 2025 and the progress culminated in the new paper published at this prestigious theoretical computer science conference.
Huge congratulations to the team on this achievement.