Colloquium: Tuesday May 27, 2025. Speaker: Sergey Komech (Ben Gurion). Title: “Optimal list-recoverability via alphabet permutation codes”.
Speaker: Sergey Komech (Ben Gurion)
Place: Room 614, Education and Sciences Building, University of Haifa
Date and Time: May 20, 2025, 14:00-15:00
Title: Optimal list-recoverability via alphabet permutation codes
Abstract: See attached PDF.
Zoom link: https://us02web.zoom.us/j/87282501214?pwd=gnoO4TOG9LKBQJrfQ89Od7nUkoy0S3.1
Meeting ID: 872 8250 1214
Passcode: 009572
A basic problem in the Coding theory is to transfer information over a noisy channel so that the original codeword can be recovered from the received word that can have some bits corrupted by noise. List-decoding and list-recovery are generalizations of unique decoding, when it is allowed for a receiver to recover a list of words that should contain the original codeword. List-recovery is more general, and it has been studied less than list-decoding.
It is known that list-recovery with non-exponential list size is possible if the rate of a code is $R = 1 – h_{q,\ell}(\rho) – \varepsilon$, where $h_{q,\ell}(\cdot)$ is the $(q,\ell)$-\textit{ary entropy}.
{\it Elias Bound} for list-recovery is presented by the list size $L = O\,(\frac{\ell}{\varepsilon})$, which is achieved by Plain Random Codes (PRC). PRC hit the desired list size, but they need exponential randomness to be described.
We construct a new family of codes that requires only polynomial randomness yet achieves $(\rho,\ell,L)$-list-recoverability at the aforementioned rate, with list size $L \approx \frac{\ell}{\varepsilon}$. In contrast, every previous construction using polynomial randomness requires an exponentially larger list size. Our approach extends earlier work by Li and Wootters (2021) on the list-decodability of random linear binary codes.
Joint work with Jonathan Mosheiff.
