Computer Science/Discrete Mathematics Seminar II

The GM-MDS conjecture

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.

Date & Time

November 06, 2018 | 10:30am – 12:30pm

Location

West Building Lecture Hall

Affiliation

University of California San Diego