Rank bounds for design matrices with applications

Rank bounds for design matrices with applications

-
Zeev Dvir, Princeton University
Fine Hall 224

We prove a lower bound on the rank of sparse matrices whose pattern of zeros and non zeros satisfies a certain 'design' like property. Namely, if the intersections of the supports of different columns are small compared to the size of the individual supports. This bound holds over fields of large characteristic or characteristic zero. As an application of this bound we get new robust generalizations of the well-known Sylvester-Gallai theorem which limits the way lines can intersect in $R^d$. Another application is an impossibility result for 2-query Locally-Correctable-Codes (LCCs) over fields of large characteristic. These codes, which do exist over fields of small characteristic, play an important role in theoretical computer science and understanding the limitations of q-query codes (for arbitrary q) is a major open problem. Our results show an interesting separation depending on the characteristic of the field for the 2-query case.Joint work with Boaz Barak (MSR), Avi Wigderson (IAS) and Amir Yehudayoff (Technion).