Explicit Maximally Recoverable Codes With Locality

DOI10.1109/TIT.2014.2332338MaRDI QIDQ2986142zbMATH OpenOpenAlexFDO

Authors Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4150

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Abstract: Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally-recoverable if it corrects all erasure patterns which are information theoretically recoverable given the code topology. In this paper we present explicit families of maximally-recoverable codes with locality. We also initiate the study of the trade-off between maximal recoverability and alphabet size.

Cited in

(23)

• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Optimal binary linear locally repairable codes with disjoint repair groups
• Codes in the sum-rank metric: fundamentals and applications
• scientific article; zbMATH DE number 7561561 (Why is no real title available?)
• Locally recoverable \(J\)-affine variety codes
• A Family of Optimal Locally Recoverable Codes
• Theory of supports for linear codes endowed with the sum-rank metric
• Anticode-based locally repairable codes with high availability
• Private information retrieval from locally repairable databases with colluding servers
• Codes for Distributed Storage
• Linear programming bounds for distributed storage codes
• Locally maximal recoverable codes and LMR-LCD codes
• Locally recoverable codes correcting many erasures over small fields
• A construction of maximally recoverable codes
• Random construction of partial MDS codes
• New upper bounds and constructions of multi-erasure locally recoverable codes
• Rank-metric codes and their applications
• A general family of MSRD codes and PMDS codes with smaller field sizes from extended Moore matrices
• New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
• Maximally Recoverable Codes for Grid-like Topologies
• Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture
• Tighter bounds on the independence number of the Birkhoff graph
• Constructing Partial MDS Codes from Reducible Algebraic Curves

This page was built for publication: Explicit Maximally Recoverable Codes With Locality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986142)