2019/05/06 by Li, Ray, Wootters, Mary
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/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(t0.585 √(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 < √(N). We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.