
arXiv: 1905.02270
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 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.
22 pages; A previous version claimed that a lifted code is exactly the span of all good monomials, but in fact the span of all good monomials only forms a subset of the lifted code. This does not change our main result
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), PIR code, Computational Complexity (cs.CC), 004, Computer Science - Computational Complexity, Lifted codes, Disjoint repair group property, Coding theory, Multiplicity codes, ddc: ddc:004
FOS: Computer and information sciences, Computer Science - Information Theory, Information Theory (cs.IT), PIR code, Computational Complexity (cs.CC), 004, Computer Science - Computational Complexity, Lifted codes, Disjoint repair group property, Coding theory, Multiplicity codes, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
