ICTS:31723

Video URL

GAP codes

GAP codes

(2025). GAP codes. SciVideos. https://youtu.be/4d6S5ND-RQg

GAP codes. SciVideos, May. 04, 2025, https://youtu.be/4d6S5ND-RQg 

          @misc{ scivideos_ICTS:31723,
            doi = {},
            url = {https://youtu.be/4d6S5ND-RQg},
            author = {},
            keywords = {},
            language = {en},
            title = {GAP codes},
            publisher = {},
            year = {2025},
            month = {may},
            note = {ICTS:31723 see, \url{https://scivideos.org/icts-tifr/31723}}
          }
Swastik Kopparty
Talk numberICTS:31723
Source RepositoryICTS-TIFR

Abstract

GAP codes are error-correcting codes based on evaluating degree-d m-variate polynomials at some
geometrically arranged points in F_q^m. For m constant and any epsilon > 0, these codes can achieve rate 1-epsilon and distance Omega(1).
For Reed-Muller codes, where the evaluation points form all of F_q^m, the rate is is exponentially small in $m$.

GAP codes turn out to have a a very simple description from the point of view of HDXs: they are Tanner codes on the complete $m$-dimensional complex with Reed-Solomon codes as the inner code.

I will talk about their construction, how to decode them, and the somewhat surprising fact that despite having much fewer evaluation points than Reed-Muller codes, GAP codes are also locally testable with O(n^{1/m}) queries.

Joint work with Harry Sha and Mrinal Kumar
(Based on part of this paper: https://arxiv.org/abs/2410.13470 )