Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Boaz Barak, Zeev Dvir, Avi Wigderson +1

A (q,k,t)-design matrix is an m x 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 leas…