Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture

DOI10.1137/20M1323345MaRDI QIDQ5009787zbMATH OpenOpenAlexWikidataFDO

Authors Shachar Lovett

Publication date 6 August 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/20m1323345

zbMATH Keywords

coding theoryGM-MDS conjectureMDS matricespolynomialsReed-Solomon codes

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Linear codes (general theory) (94B05)

Recommendations

• On sets of vectors of a finite vector space in which every subset of basis size is a basis. II
• Inclusion matrices and the MDS conjecture
• On lowest density MDS codes
• On MDS codes via Cauchy matrices
• scientific article; zbMATH DE number 703977

Cites work

• A Family of Optimal Locally Recoverable Codes
• A probabilistic remark on algebraic program testing
• A Random Linear Network Coding Approach to Multicast
• An improvement of the tree code construction
• Coding for interactive communication
• Coding for Interactive Communication Correcting Insertions and Deletions
• Deterministic coding for interactive communication
• Efficient Coding for Interactive Communication
• Explicit Maximally Recoverable Codes With Locality
• Fast algorithms for interactive coding
• Fast interactive coding against adversarial noise
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Gabidulin Codes With Support Constrained Generator Matrices
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• Linear tree codes and the problem of explicit constructions
• List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
• Maximally Recoverable Codes for Grid-like Topologies
• Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities
• Maximum distance<tex>q</tex>-nary codes
• Reed–Solomon Codes Over Small Fields With Constrained Generator Matrices
• Sparse and Balanced Reed–Solomon and Tamo–Barg Codes
• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Toward coding for maximum errors in interactive communication
• Towards deterministic tree code constructions
• Towards optimal deterministic coding for interactive communication
• Tree codes and a conjecture on exponential sums

Cited in

(6)

• The truncated and supplemented Pascal matrix and applications
• On MDS codes via Cauchy matrices
• On sets of vectors of a finite vector space in which every subset of basis size is a basis. II
• On lowest density MDS codes
• An algebraic-coding equivalence to the maximum distance separable conjecture
• Kapranov degrees

This page was built for publication: Sparse MDS matrices over small fields: a proof of the GM-MDS conjecture

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