All reports by Author Ray Li:

__
TR23-126
| 25th August 2023
__

Omar Alrabiah, Venkatesan Guruswami, Ray Li#### AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets

__
TR23-125
| 25th August 2023
__

Omar Alrabiah, Venkatesan Guruswami, Ray Li#### Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields

__
TR21-079
| 9th June 2021
__

Venkatesan Guruswami, Xiaoyu He, Ray Li#### The zero-rate threshold for adversarial bit-deletions is less than 1/2

__
TR20-168
| 11th November 2020
__

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters#### Improved List-Decodability of Reedâ€“Solomon Codes via Tree Packings

Omar Alrabiah, Venkatesan Guruswami, Ray Li

A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate $R$ codes are not list-decodable using list-size $L$ beyond an error fraction $\frac{L}{L+1} (1-R)$ (the Singleton bound being the case of $L=1$, i.e., unique decoding). We prove that in order to approach this bound for ... more >>>

Omar Alrabiah, Venkatesan Guruswami, Ray Li

Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a ... more >>>

Venkatesan Guruswami, Xiaoyu He, Ray Li

We prove that there exists an absolute constant $\delta>0$ such any binary code $C\subset\{0,1\}^N$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{\poly\log N}$ and thus have rate asymptotically approaching $0$. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate ... more >>>

Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>