ECCC-Report TR12-138https://eccc.weizmann.ac.il/report/2012/138Comments and Revisions published for TR12-138en-usFri, 02 Nov 2012 09:36:00 +0200
Paper TR12-138
| Improved rank bounds for design matrices and a new proof of Kelly's theorem |
Zeev Dvir,
Shubhangi Saraf,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2012/138We 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. Fri, 02 Nov 2012 09:36:00 +0200https://eccc.weizmann.ac.il/report/2012/138