Reed-Solomon (RS) codes were recently shown to exhibit an intriguing \emph{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. Here  $\delta$ is the proximity parameter which can be taken to be the Johnson radius $1-\sqrt{R}$ of the RS code ($R$ being the code rate), matching its best known list-decodability. Proving proximity gaps beyond the Johnson radius, and in particular approaching $1-R$ (which is best possible), has been posed multiple times as a challenge with significant practical consequences to the efficiency of SNARKs. In this work, we show that most codes in the literature that have been shown to achieve list-decoding capacity, i.e., are \emph{list-decodable} up to a fraction of errors approaching $1-R$, exhibit proximity gaps for $\delta<1-R$. This includes folded Reed-Solomon codes, univariate multiplicity codes, random linear codes, and random Reed-Solomon codes. Based on joint work with Venkatesan Guruswami.

Short Bio: Rohan is a PhD student in the Theory of Computation Group at MIT, where he is advised by Yael Tauman Kalai. His research interests are broadly in error correction, proof systems, and more generally theoretical CS. Rohan has been a friend of STCS since his undergraduate days, when he spent a few months here as an intern.