A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry basecode of block-length q to a lifted-code of block-length qm, for arbitrary integer m. The construction generalizes the way degree-d, univariate polynomials evaluated over the qelement field (also known as Reed-Solomon codes) are"lifted" to degree-d, m-variate polynomials (Reed-Muller codes). A number of properties are established: Rate The rate of the degree-lifted code is approximately a 1 m! -fraction of the rate of the base-code. Distance The relative distance of the degree-lifted code is at least as large as that of the base-code. This is proved using a generalization of the Schwartz-Zippel Lemma to degree-lifted Algebraic-Geometry codes . Local correction If the base code is invariant under a group that is "close" to being doubly-transitive (in a precise manner defined later ) then the degree-lifted code is locally correctable with query complexity at most q2. The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affinelines in the local correction procedure of Reed-Muller codes. Taking a concrete illustrating example, we show that degreelifted Hermitian codes form a family of locally correctable codes over an alphabet that is significantly smaller than that obtained by Reed-Muller codes of similar constant rate, message length, and distance.

Original languageEnglish (US)
Title of host publicationSTOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing
Pages833-842
Number of pages10
DOIs
StatePublished - Jul 11 2013
Event45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States
Duration: Jun 1 2013Jun 4 2013

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other45th Annual ACM Symposium on Theory of Computing, STOC 2013
CountryUnited States
CityPalo Alto, CA
Period6/1/136/4/13

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algebraic geometry codes
  • Error correcting codes
  • Locally correctable codes
  • Locally decodable codes

Fingerprint Dive into the research topics of 'A new family of locally correctable codes based on degree-lifted algebraic geometry codes'. Together they form a unique fingerprint.

  • Cite this

    Ben-Sasson, E., Gabizon, A., Kaplan, Y., Kopparty, S., & Saraf, S. (2013). A new family of locally correctable codes based on degree-lifted algebraic geometry codes. In STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing (pp. 833-842). (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/2488608.2488714