IMPROVED RANK BOUNDS for DESIGN MATRICES and A NEW PROOF of KELLY'S THEOREM

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

Research output: Contribution to journalArticle

17 Scopus citations

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 [Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. Proceedings of the 43rd annual ACM symposium on Theory of computing, STOC 11, (ACM, NY 2011), 519-528] 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.

Original languageEnglish (US)
Article numbere4
JournalForum of Mathematics, Sigma
Volume2
DOIs
StatePublished - Feb 1 2014

All Science Journal Classification (ASJC) codes

  • Analysis
  • Theoretical Computer Science
  • Algebra and Number Theory
  • Statistics and Probability
  • Mathematical Physics
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'IMPROVED RANK BOUNDS for DESIGN MATRICES and A NEW PROOF of KELLY'S THEOREM'. Together they form a unique fingerprint.

  • Cite this