Grainger College of Engineering, All Events

Abstract:  A proximity gap for a code C says that every affine subspace either consists almost entirely of words close to C, or contains almost no such words. Proximity gaps are a key ingredient in the soundness analysis of FRI-based interactive oracle proofs and succinct arguments. Prior work (Ben-Sasson et al.) established proximity gaps for Reed–Solomon codes up to the Johnson radius, inherently limited by the Guruswami–Sudan list-decoding bound. We present optimal proximity gaps for Folded Reed–Solomon codes that reach list-decoding capacity: for any rate R and slack η > 0, we obtain a (1−R−η, ε)-proximity gap with ε vanishing in the field size. The proof introduces a new mechanism called line stitching, which replaces the small-list structure used at the Johnson radius with a cluster-based argument inspired by the subspace-design property of FRS codes. I will focus on the main proof techniques, the pruning lemma, the pinning argument, and the line-to-affine lifting, and try to convey the geometric and algebraic intuitions behind them.