Theory Seminar: Lenny Liu, "Optimal Proximity Gaps for Folded Reed-Solomon Codes via Subspace Designs."
- Sponsor
- Theory and Algorithms Research Area
- Speaker
- Lenny Liu
- Contact
- Makrand Sinha
- msinha@illinois.edu
- Originating Calendar
- Siebel School Speakers Calendar
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.