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 generalize their construction by introducing lifted multiplicity codes, 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 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. |
Year | Venue | DocType |
---|---|---|
2019 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1905.02270 | 0 | 0.34 |
References | Authors | |
0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ray Li | 1 | 0 | 2.03 |
Mary Wootters | 2 | 172 | 25.99 |