A Student's View of Locally Repairable Codes
summary
Student-oriented survey argues that locality forces the same gap to erasure‑channel capacity as LDPC codes, proving locality must grow like log(1/ε) when rate is ε from capacity using entropy/Fano and martingale concentration arguments. Defines a graph storage capacity, shows a duality with index coding (capacity ≈ n minus index length), gives a 4‑node example where nonlinear repair stores 2.32193 bits (five codewords), and uses matching / vertex‑cover bounds to get a simple 2‑approximation.
AI-written summary · about
chapters (18)
- 0:00Intro
- 1:09Lightning Talk: An information storage graph
- 1:55Disclaimer
- 2:15Locality of Codeword Symbols
- 5:45Erasure channel
- 6:54The output entropy
- 8:41Concentration of output entropy
- 9:17Bottom-line
- 11:00How much storage is possible?
- 13:362 bits continued...
- 13:57Reminder from lightning talk
- 14:43It's quite practical (ask Google)
- 15:49Reduction to a dual problem! Index coding
- 18:35RDSS and INDEX
- 19:33Network information flow
- 20:11Undirected graphs
- 22:02RDSS with minimum distance
- 24:13Acknowledgements
related talks
17mPractical Design Considerations for Wide Locally Recoverable Codes (LRCs)
30mExact Completeness of LP Hierarchies for Linear Codes
26mLow-bandwidth recovery of linear functions of Reed-Solomon-encoded data
24mOpenEC: Toward Unified and Configurable Erasure Coding Management...
01h 14mErasure Coding at Scale
47mService Rates Of Mds Codes & Fractional Matchings In Quasi-Uniform Hypergraphs
17mParaRC: Embracing Sub-Packetization for Repair Parallelization in MSR-Coded Storage
43mResizable Sketches