Maximally Recoverable Codes
summary
Defines three MRC families—locality, hierarchical locality, and tensor/product topologies—and gives explicit constructions that use k-wise independence and linearized Reed‑Solomon/Gabidulin ingredients; shows hierarchical MRCs by choosing local, mid‑level and global parities from nested fields and proves they meet the maximal recoverability condition. Highlights a large gap between existential lower bounds (poly in n) and best constructions, cites the product case reducible to a matching condition and links higher‑order MDS to optimal list‑decodability as a major open construction problem.
AI-written summary · about
chapters (6)
- 0:00Introduction and motivation
- 1:40Locally repairable codes
- 15:04Construction techniques
- 22:17Matroid and hierarchy
- 28:00Product topologies and research
- 31:37Q&A and concluding remarks
related talks
27mList Recovery and Local Decoding of Expander Codes
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
11mExploiting Combined Locality for Wide-Stripe Erasure Coding in Distributed Storage
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
17mParaRC: Embracing Sub-Packetization for Repair Parallelization in MSR-Coded Storage
31mMulti-version Coding and Shared Memory Emulation
58mThe Communication Complexity Landscape of Information-theoretic MPC
15mSelectiveEC: Selective Reconstruction in Erasure-coded Storage Systems