A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up to list decoding capacity in their natural setting of parameters. A curious aspect of this work was that unlike most list decoding ... more >>>

Reed-Solomon (RS) codes were recently shown to exhibit an intriguing $\textit{proximity gap}$ phenomenon. Specifically, given a collection of strings with some algebraic structure (such as belonging to a line or affine space), either all of them are $\delta$-close to RS codewords, or most of them are $\delta$-far from the code. ... more >>>

We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the \emph{batch language} $\mathcal{L}^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity ... more >>>

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they ... more >>>