Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TRACE CODE:
Reports tagged with Trace code:
TR21-139 | 24th September 2021
Venkatesan Guruswami, Jonathan Mosheiff

#### Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity

Revisions: 2

We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the ... more >>>

ISSN 1433-8092 | Imprint