Lifted Multiplicity Codes and the Disjoint Repair Group Property
Ray Li, Mary K. Wootters · IEEE Transactions on Information Theory · 2020
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 calllifted 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. As a corollary, they also give better tradeoffs for PIR codes in the same parameter regimes. More precisely, we show that, for$t\le \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.