Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A question arising in the study of codes for distributed storage is the following combinatorial/algebraic problem. Let A be a k x n matrix (k less than n). Some of the elements of A are set to 0, while the rest are left empty. The goal is to fill the non-zero elements of A with field elements from some finite field F_q, such that all k x k minors of A that can potentially be nonsingular, will be nonsingular. The main question is: what is the minimal field size needed to achieve that?

A simple probabilistic argument shows that field of size {n choose k} is always sufficient. However, it could potentially be much smaller. For example, if A has no zeros, then the Reed-Solomon codes (that is, Vandermonde matrices) satisfy the requirements, and exist over fields of size >=n.

I will describe two results:

1. Assume that A has so few zeros, so that any k x k minor can potentially be nonsingular. There is a nice combinatorial condition which characterizes this case. Dau et al. conjectured that in this case, there are "algebraic" constructions over small fields with the prescribed zeros. I will prove this conjecture.

2. In a few cases, we know how to prove the no "algebraic" construction exists, in the sense that an exponential field size is necessary. I will describe such a case, where the proof has surprising relations to the chromatic number of the Birkhoff polytope.

The second result is based on a joint work with Daniel Kane and Sankeerth Rao.

Papers:
https://arxiv.org/abs/1803.02523

https://arxiv.org/abs/1702.05773