Locally Recoverable Code Constructions and Some Extensions
summary
Constructs LRCs that meet the distance bound with equality while keeping field size ~ n, using a Reed‑Solomon style encoding where a degree‑(r+1) polynomial G is constant on r+1 sized cosets and the encoding polynomial F has coefficient polynomials constant on those cosets. Example: a 9,4 code over F13 achieves distance 5 and locality 2 (vs RS locality 4, distance 6). Shows multiple disjoint recovering sets by intersecting subspace constructions, analyzes cyclic/subfield subcodes (example: locality 14 → 7 on restriction to F2) and mentions AG/subfield extensions.
AI-written summary · about
chapters (15)
- 0:00Intro
- 0:32Limitations of Reed-Solomon Codes
- 1:09Locally Recoverable Codes (LRC)
- 2:03Locality and Minimum Distance
- 3:02Previous Constructions
- 3:55(n,k,r)LRC - Easy Cases
- 5:23LRC Construction Properties
- 5:53Intuition behind the LRC Construction
- 7:56Optimal (n,k,r)LRC Construction
- 20:49The Ingredients
- 22:22Multiple Recovering Sets
- 23:22Optimal LRC - Example 2
- 25:59LRC codes over a small field
- 28:03Subfield Subcodes-Surprising observation
- 31:09LRC codes on algebraic curves
related talks
17mPractical Design Considerations for Wide Locally Recoverable Codes (LRCs)
26mLow-bandwidth recovery of linear functions of Reed-Solomon-encoded data
30mExact Completeness of LP Hierarchies for Linear Codes
24mRecovery from Non-Decomposable Distance Oracles
17mParaRC: Embracing Sub-Packetization for Repair Parallelization in MSR-Coded Storage
24mWhen Less Is More: Consequence-Finding in a Weak Theory of Arithmetic
47mService Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
36mOptimizing Relational Programs II