ECCC-Report TR12-148https://eccc.weizmann.ac.il/report/2012/148Comments and Revisions published for TR12-148en-usWed, 21 May 2014 11:24:45 +0300
Revision 1
| 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
https://eccc.weizmann.ac.il/report/2012/148#revision1We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" to degree-$d$, $m$-variate polynomials (Reed-Muller codes). Three properties are established:
{\bf Rate} The rate of the degree-lifted code is approximately a $\frac{1}{m!}$-fraction of the rate of the base-code.
{\bf 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.
As a first concrete example, lifting the AG codes of Garcia and Stichtenoth [J. Number Theory `96] results in Reed-Muller-like codes but over constant sized alphabets, such codes are interesting in the search for probabilistically checkable proofs (PCPs) with constant rate and polynomially small query complexity.
{\bf 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 $q^2$. The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affine-lines in the local correction procedure of Reed-Muller codes.
Taking a second concrete example, we show that degree-lifted 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.
Wed, 21 May 2014 11:24:45 +0300https://eccc.weizmann.ac.il/report/2012/148#revision1
Paper TR12-148
| 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
https://eccc.weizmann.ac.il/report/2012/148We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" to degree-$d$, $m$-variate polynomials (Reed-Muller codes). Three properties are established:
{\bf Rate} The rate of the degree-lifted code is approximately a $\frac{1}{m!}$-fraction of the rate of the base-code.
{\bf 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.
As a first concrete example, lifting the AG codes of Garcia and Stichtenoth [J. Number Theory `96] results in Reed-Muller-like codes but over constant sized alphabets, such codes are interesting in the search for probabilistically checkable proofs (PCPs) with constant rate and polynomially small query complexity.
{\bf 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 $q^2$. The automorphisms of the base-code are crucially used to generate query-sets, abstracting the use of affine-lines in the local correction procedure of Reed-Muller codes.
Taking a second concrete example, we show that degree-lifted 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.
Wed, 07 Nov 2012 17:34:08 +0200https://eccc.weizmann.ac.il/report/2012/148