Optimal Proximity Gaps for Subspace-Design Codes and (Random) Reed-Solomon Codes

Reed-Solomon (RS) codes were recently shown to exhibit an intriguing 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 δ-close to RS codewords, or most of them are δ-far from the code. Here δ is the proximity parameter which can be taken to be the Johnson radius 1−√R of the RS code (R being the code rate), matching its best known list-decodability. Proximity gaps play a crucial role in the soundness analysis of Interactive Oracle Proof (IOP) protocols used in Succinct Non-Interactive Arguments of Knowledge (SNARKs) and the resulting proof sizes.