Nonlinear Repair Schemes of Reed-Solomon Codes

on YouTube ↗29m

" summary

Claims a nonlinear repair method for Reed‑Solomon codes over prime fields, proving almost all 2‑dimensional RS codes are asymptotically MSR for any number of helpers and giving an explicit construction for general K (helpers up to N/2) whose bandwidth asymptotically achieves the cut‑set bound. Technique partitions F_p and has each helper send a set index (bandwidth ≈ (N−1)·log(p/T)); also proves a new lower bound tightening the cut‑set bound, so constructions and limits both hold.

AI-written summary · about

" chapters (23)

1. 0:00Intro
2. 0:27Coding For Distributed Storage Systems
3. 1:27Linear Codes and Linear MDS codes
4. 3:20Coding For Storage
5. 4:30Problem: A single node fails
6. 4:59Repair Schemes
7. 6:18Bandwidth
8. 7:35The Repair Problem
9. 8:39Trivial Repair: MDS property
10. 11:17Cut-Set bound and MSR Codes
11. 12:15Reed Solomon codes
12. 13:28A Polynomial Interpolation Problem
13. 14:18RS codes. Known results
14. 16:19Reduce the Alphabet Size
15. 17:13Informal results. First nonlinear repair scheme
16. 18:30Informal result - A new lower bound
17. 19:13Non Linear Repair - Intuition
18. 20:07Proof Idea
19. 20:38Repair Scheme for the nth node
20. 22:25Repair Scheme. Condition
21. 23:09Repair Scheme - Condition
22. 26:49What We Need?
23. 27:38Open Questions