Rohan Goyal

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon>0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optim...