The GM-MDS conjecture

 Computer Science/Discrete Mathematics Seminar II Topic: The GM-MDS conjecture Speaker: Shachar Lovett 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.