Paper Info
Title
Lifted Multiplicity Codes and the Disjoint Repair Group Property
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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">lifted multiplicity codes</i> . 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> -disjoint-repair-group property than previously known constructions. As a corollary, they also give better tradeoffs for PIR codes in the same parameter regimes. More precisely, we show that, for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t\le \sqrt {N}$ </tex-math></inline-formula> , lifted multiplicity codes with length <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> and redundancy <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(t^{0.585} \sqrt {N})$ </tex-math></inline-formula> have the property that any symbol of a codeword can be reconstructed in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$t &lt; \sqrt {N}$ </tex-math></inline-formula> . We also give an alternative analysis of lifted Reed-Solomon codes using dual codes, which may be of independent interest.
Year
DOI
Venue
2021
10.1109/TIT.2020.3034962
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Error correction codes,lifted codes,multiplicity codes,locality,disjoint repair groups
Journal
67
Issue
ISSN
Citations 
2
0018-9448
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Ray Li133.09
Mary Wootters217225.99