2026-07-22T14:19:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11253 2024-03-06T10:47:48Z ddc:004 open_access

Lifted Multiplicity Codes and the Disjoint Repair Group Property Li, Ray Wootters, Mary Lifted codes Multiplicity codes Disjoint repair group property PIR code Coding theory 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, for t <=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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ray Li and Mary Wootters 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.38 urn:nbn:de:0030-drops-112539 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.38 eng https://creativecommons.org/licenses/by/3.0/legalcode