We show that Reed-Solomon codes of dimension $k$ and block length $n$ over any finite field $\mathbb{F}$ can be deterministically list decoded from agreement $\sqrt{(k-1)n}$ in time $\text{poly}(n, \log |\mathbb{F}|)$.

Prior to this work, the list decoding algorithms for Reed-Solomon codes, from the celebrated results of ... more >>>

This paper is about the proximity gaps phenomenon for Reed-Solomon codes.
Very roughly, the proximity gaps phenomenon for a code $\mathcal C \subseteq \mathbb F_q^n$ says that for two vectors $f,g \in \mathbb F_q^n$, if sufficiently many linear combinations $f + z \cdot g$ (with $z \in \mathbb F_q$) ... more >>>

A large alphabet Locally Decodable Code (LDC) $C:\Sigma^{k} \to \Sigma'^{n}$, where $\Sigma'$ may be large, is a code where each symbol of $x$ can be decoded by making few queries to a noisy version of $C(x)$. The rate of $C$ is its information rate, namely $\frac{k \log (|\Sigma|) }{n \log ... more >>>