Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture

DOI10.1137/20M1323345zbMath1495.11130OpenAlexW3184708196WikidataQ123356578 ScholiaQ123356578MaRDI QIDQ5009787

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

polynomialsReed-Solomon codescoding theoryMDS matricesGM-MDS conjecture

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• An improvement of the tree code construction
• Linear tree codes and the problem of explicit constructions
• A probabilistic remark on algebraic program testing
• Towards deterministic tree code constructions
• List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise
• Toward Coding for Maximum Errors in Interactive Communication
• Explicit Maximally Recoverable Codes With Locality
• A Family of Optimal Locally Recoverable Codes
• Efficient Coding for Interactive Communication
• Tree codes and a conjecture on exponential sums
• Coding for interactive communication
• A Random Linear Network Coding Approach to Multicast
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Coding for Interactive Communication Correcting Insertions and Deletions
• Towards Optimal Deterministic Coding for Interactive Communication
• Maximally Recoverable Codes for Grid-like Topologies
• Sparse and Balanced Reed–Solomon and Tamo–Barg Codes
• Gabidulin Codes With Support Constrained Generator Matrices
• Maximally Recoverable LRCs: A Field Size Lower Bound and Constructions for Few Heavy Parities
• Reed–Solomon Codes Over Small Fields With Constrained Generator Matrices
• The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes
• Deterministic coding for interactive communication
• Fast Interactive Coding against Adversarial Noise
• Maximum distance<tex>q</tex>-nary codes
• Fast Algorithms for Interactive Coding

This page was built for publication: Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture