Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-047 | 20th March 2018 21:07

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

RSS-Feed




Revision #1
Authors: Shachar Lovett
Accepted on: 20th March 2018 21:07
Downloads: 125
Keywords: 


Abstract:

An MDS matrix is a matrix whose minors all have full rank. A question arising in coding theory is what zero patterns can MDS matrices have. There is a natural combinatorial characterization (called the MDS condition) which is necessary over any field, as well as sufficient over very large fields by a probabilistic argument.

Dau et al. (ISIT 2014) conjectured that the MDS condition is sufficient over small fields as well, where the construction of the matrix is algebraic instead of probabilistic. This is known as the GM-MDS conjecture. Concretely, if a $k \times n$ zero pattern satisfies the MDS condition, then they conjecture that there exists an MDS matrix with this zero pattern over any field of size $|\mathbb{F}| \ge n+k-1$. In recent years, this conjecture was proven in several special cases. In this work, we resolve the conjecture.



Changes to previous version:

Added more explanations and discussions


Paper:

TR18-047 | 7th March 2018 06:39

A proof of the GM-MDS conjecture





TR18-047
Authors: Shachar Lovett
Publication: 11th March 2018 16:13
Downloads: 486
Keywords: 


Abstract:

The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture.



ISSN 1433-8092 | Imprint