Rank Bounds for Design Matrices

Опубликовано 17 августа 2016, 22:05

A (q,k,t)-design matrix is an m by n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: Each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. Our main theorem is a lower bound of n - (qtn/2k)^2 on the rank of such matrices over fields of characteristic zero (or sufficiently large finite characteristic).This result is motivated by questions regarding matrix rigidity and locally correctable codes. Using this theorem we derive the following three applications: (1) Our first application is to linear 2-query locally correctable codes. These are error correcting codes in which each codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Over finite fields of small characteristic constructions of such codes with exponential encoding length are known. We show, using our rank theorem, that these codes do not exist over fields of large characteristic or characteristic zero regardless of the encoding length. This theorem comes as an extension of the following result in combinatorial geometry: (2) We prove a quantitative analog of the Sylvester Gallai theorem: Let v_1,...,v_m be a set of points in C^d such that for every i in [m] there exists at least delta * m values of j in [m] such that the line through v_i,v_j contains a third point in the set. We show that in this case the dimension of the set is at most O(1/delta^2). The only case that was studied before is when delta is very close to one. (3) Another variant of the Sylvester Gallai theorem that we strengthen is the Motzkin-Rabin Theorem. In this variant the points are each colored by either red or blue. The assumption is that for every blue (red) point there is a delta-fraction of the blue (red) points such that the line connecting them contains a point of the opposite color. Our theorem gives a bound of O(1/delta^4) on the dimension of the set of points in this case. Joint work with Boaz Barak, Avi Wigderson and Amir Yehudayoff