Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data
summary
Shows a concrete scheme for Reed–Solomon codes that computes any linear function λ·f by downloading only o(b) bits, specifically Θ(b / log b) bits when using all n = q^t evaluation points of the extension field F_{q^t}. Nodes return short base-field vectors via s×t matrices A_j and the user combines them with t×s matrices R_j to recover λ·f; s is constant for fixed rate. Works despite up to about 1−r fraction of missing nodes and matches a linear-scheme lower bound of order b / log b for MDS codes.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:16Overview
- 2:22Distributed Storage with an Error-Correcting Code
- 5:44Our Result - Intuition
- 8:37Our Result - Theorem Statement
- 9:51Our Result - Theorem Details Our there is more general
- 13:39Extension Field Elements as Vectors and Matrices
- 15:23Subfield-Linear Recovery Schemes for Linear Codes
- 21:38Construction for Reed-Solomon Codes
- 22:46Future Work
related talks
34mLocally Recoverable Code Constructions and Some Extensions
17mPractical Design Considerations for Wide Locally Recoverable Codes (LRCs)
27mA Student's View of Locally Repairable Codes
43mResizable Sketches
24mRecovery from Non-Decomposable Distance Oracles
47mService Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
01h 14mErasure Coding at Scale
01h 02mThe Complexity of Dynamic Least-Squares Regression