Name
Title | ||
|---|---|---|
A new family of locally correctable codes based on degree-lifted algebraic geometry codes |
Abstract | ||
|---|---|---|
We describe new constructions of error correcting codes, obtained by \"degree-lifting\" a short algebraic geometry base-code 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 q-element field (also known as Reed-Solomon codes) are \"lifted\" to degree-d, m-variate polynomials (Reed-Muller codes). A number of properties are established: The rate of the degree-lifted code is approximately a 1/m!-fraction of the rate of the base-code. 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 affine-lines in the local correction procedure of Reed-Muller codes. Taking a concrete illustrating 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2488608.2488714 | Proceedings of the forty-fifth annual ACM symposium on Theory of computing |
Keywords | DocType | Citations |
reed-muller code,similar constant rate,degree-lifted algebraic geometry code,correctable code,degree-lifted code,block-length q,degree-lifted algebraic-geometry code,short algebraic geometry base-code,degree-lifted hermitian code,new family,reed-solomon code,base code | Journal | 3 |
PageRank | References | Authors |
0.48 | 56 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eli Ben-Sasson | 1 | 1641 | 86.98 |
| Ariel Gabizon | 2 | 156 | 13.97 |
| Yohay Kaplan | 3 | 3 | 0.48 |
| Swastik Kopparty | 4 | 384 | 32.89 |
| Shubhangi Saraf | 5 | 263 | 24.55 |