BARC talk by Oscar Sprumont

Wednesday, August 28, 2024, Oscar Sprumont, PhD Student at the University of Washington, US, will give a talk on "List decoding capacity implies BSC capacity".

Abstract:
The capacity of a communication channel is the logarithm of the size of the largest code that can reliably be used for communication on that channel. It is well-known that the capacity of the random-error channel under unique decoding is exactly the same as the capacity of the adversarial-error channel under list decoding. (By unique decoding, we mean that the receiver needs to correctly output the sent codeword; by list decoding, we mean that the receiver need only output a small list of potential codewords, with the guarantee that the sent codeword is in that list). We give an explanation for this phenomenon. Let C be any q-ary linear code with minimum distance larger than q^3. We show that if C is optimal for list-decoding adversarial errors, then C is also optimal for uniquely recovering from random errors. Based on joint work with Francisco Pernice and Mary Wootters.

Bio:
Oscar Sprumont is a PhD student at the University of Washington, advised by Anup Rao. He previously received his Bachelor of Science from McGill University. His main research interests are coding theory, complexity theory, and combinatorics.

Host:
Amir Yehudayoff