License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.38
URN: urn:nbn:de:0030-drops-112539
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11253/
Go to the corresponding LIPIcs Volume Portal

Li, Ray ; Wootters, Mary

Lifted Multiplicity Codes and the Disjoint Repair Group Property

pdf-format:
LIPIcs-APPROX-RANDOM-2019-38.pdf (0.6 MB)

Abstract

Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the t-disjoint-repair-group property than previously known constructions. More precisely, we show that, for t <=sqrt{N}, lifted multiplicity codes with length N and redundancy O(t^{0.585} sqrt{N}) have the property that any symbol of a codeword can be reconstructed in t different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant t < sqrt{N}. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.

BibTeX - Entry

@InProceedings{li_et_al:LIPIcs:2019:11253,
  author =	{Ray Li and Mary Wootters},
  title =	{{Lifted Multiplicity Codes and the Disjoint Repair Group Property}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11253},
  URN =		{urn:nbn:de:0030-drops-112539},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.38},
  annote =	{Keywords: Lifted codes, Multiplicity codes, Disjoint repair group property, PIR code, Coding theory}
}

Keywords: Lifted codes, Multiplicity codes, Disjoint repair group property, PIR code, Coding theory
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI