Improved rank bounds for design matrices and a new proof of Kelly's theorem

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study the rank of complex sparse matrices in which the supports of different columns have small intersections. The rank of these matrices, called design matrices, was the focus…