|Computer Science/Discrete Mathematics Seminar II|
|Topic:||The GM-MDS conjecture|
|Affiliation:||University of California San Diego|
|Date:||Tuesday, November 6|
|Time/Room:||10:30am - 12:30pm/West Building Lecture Hall|
A $k \times n$ matrix $(k<n)$ is an MDS matrix if any k columns in it are linearly independent. There are standard constructions of MDS matrices, such as Vandermonde matrices, which used for error correcting codes (they generate Reed-Solomon codes). There is interest in the coding community in *sparse* MDS matrices, with specific coordinates set to zero based on the underlying code topology. A natural question arises: when do these exist? It turns out that there is a simple combinatorial condition which is both necessary and sufficient over exponentially large fields. The GM-MDS conjecture of Dau, Song and Yuen (ISIT 2014) is that the same combinatorial conditions suffice over much smaller fields (of size linear in $k,n$ instead of exponential). In this work, we resolve this conjecture.