Rank Bounds for Design Matrices, with Applications to
Combinatorial Geometry and Locally Correctable Codes
Avi Wigderson, Institute for Advanced Study, Princeton
A (q, k, t)-design matrix is an mn matrix whose pattern of zeros/non-zeros
entries 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
Our main theorem is a lower bound of n - ( qtn/k )^2 on
the rank of such matrices over fields characteristic zero (or sufficiently
large finite characteristic). This result is motivated by questions regarding
matrix rigidity, locally correctable codes and combinatorial geometry.
Using this theorem we derive the following applications.
1. A linear 2-query locally correctable code with error
rate d>0 over a field F is a subspace C of F^n such that every coordinate
can be recovered with high probability from two other ones, even if a d
fraction of the coordinates has been corrupted.
We prove that over fields of characteristic zero (or
large enough characteristic), such codes do not exist, regardless of the
encoding length n (specifically, dim(C) cannot exceed a constant of the form
poly(1/ d). This is in contrast to small finite fields where they do exsit,
e.g. the Hadamard code over GF(2) which has exponential encoding length (namely
here dim(C) increases to infinity like log n). Our impossibility result is an
extension of the following one in combinatorial geometry.
2. For a finite point set P in Euclidean space, a special
line is one containing at least 3 points from the set.
The Sylvester-Gallai theorem states that if, for every
point, the special lines through it meet all other points, then the set P is
1-dimensional (all points lie on a single line).
Szemeredi-Trotter improved it, showing that even if the
special lines through every point contain .999-fraction of all points, P must
be 1-dimensional. This may be viewed as a "unique decoding" result,
naturally suggesting to ask what happens when this fraction is reduced below
1/2. We prove a "list-decoding" of "robust" version of
these theorems as follows. If through every point, the special lines meet a
d-fraction of all other points, then dim(P) must be O(1/d^2). This upper bound
is quadratic in the trivial lower bound of dim(P) > 1/d, obtained by
spreading the points roughly evenly on 1/d generic lines. Our techniques allow
us to obtain similar generalization also to the Motzkin- Rabin theorem about
Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff