October 18, 2022. Nicolas Resch

Title: Zero-Rate Thresholds and New Capacity Bounds
for List-Decoding

Abstract: It is typically desired that an error-correcting
code has the property that, so long as a codeword is not
too corrupted, it is possible to recover the codeword.
However, this unique-decoding requirement places
fairly strict limits on the tolerable noise, especially
when one is concerned with worst-case errors.
Motivated by this (as well as their numerous applications
in theoretical computer science), list-decodable codes
have been defined and studied, which informally allow
for the recovery of a short list of possible codewords
that could have led to a given corrupted codeword.
Formally, a code is called (p, L)-list-decodable if
every radius pn Hamming ball contains less than
L codewords. 

For a given alphabet size q and a list-size L, our main
contribution consists of computing the maximum value
of p for which there exist positive rate (p,L)-list-decodable
q-ary codes, a value called the zero-rate threshold.
Denoting this value by p*, we in fact show that q-ary codes
correcting p*+epsilon fraction of errors must have constant
size (i.e., independent of the codeword length); such a result
is often called a Plotkin bound. From such a result we can
then follow a classic proof template to derive other tradeoffs
between the rate and decoding-radius for list-decodable codes.

In the talk, we will see a high level overview of how one proves
a Plotkin bound, as well as an elucidation of how certain
convexity properties play an important role.

Slides:

Comments are closed.