For every fixed finite field \F_q, p \in (0,1-1/q) and \varepsilon > 0, we prove that with high probability a random subspace C of
\F_q^n of dimension (1-H_q(p)-\varepsilon)n has the
property that every Hamming ball of radius pn has at most
O(1/\varepsilon) codewords.

This ... more >>>

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 >>>

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 >>>