### 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 q^{m}, 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 q^{2}. 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 language | English (US) |
---|---|

Title of host publication | STOC 2013 - Proceedings of the 2013 ACM Symposium on Theory of Computing |

Pages | 833-842 |

Number of pages | 10 |

DOIs | |

State | Published - Jul 11 2013 |

Event | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 - Palo Alto, CA, United States Duration: Jun 1 2013 → Jun 4 2013 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Other

Other | 45th Annual ACM Symposium on Theory of Computing, STOC 2013 |
---|---|

Country | United States |

City | Palo Alto, CA |

Period | 6/1/13 → 6/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

*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