Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-138 | 2nd November 2012 01:53

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

RSS-Feed




TR12-138
Authors: Zeev Dvir, Shubhangi Saraf, Avi Wigderson
Publication: 2nd November 2012 09:36
Downloads: 3491
Keywords: 


Abstract:

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 of a recent work by Barak et. al. (BDWY11) in which they were used to answer questions regarding point configurations. In this work we derive near-optimal rank bounds for these matrices and use them to obtain asymptotically tight bounds in many of the geometric applications. As a consequence of our improved analysis, we also obtain a new, linear algebraic, proof of Kelly's theorem, which is the complex analog of the Sylvester-Gallai theorem.



ISSN 1433-8092 | Imprint