Geodesic
IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
Forum of Mathematics, Sigma, Tome 2 (2014)

Voir la notice de l'article provenant de la source Cambridge University Press

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. [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. 
@article{10_1017_fms_2014_2,
     author = {ZEEV DVIR and SHUBHANGI SARAF and AVI WIGDERSON},
     title = {IMPROVED {RANK} {BOUNDS} {FOR} {DESIGN} {MATRICES} {AND} {A} {NEW} {PROOF} {OF} {KELLY{\textquoteright}S} {THEOREM}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {2},
     year = {2014},
     doi = {10.1017/fms.2014.2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2014.2/}
}
TY  - JOUR
AU  - ZEEV DVIR
AU  - SHUBHANGI SARAF
AU  - AVI WIGDERSON
TI  - IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
JO  - Forum of Mathematics, Sigma
PY  - 2014
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2014.2/
DO  - 10.1017/fms.2014.2
LA  - en
ID  - 10_1017_fms_2014_2
ER  - 
%0 Journal Article
%A ZEEV DVIR
%A SHUBHANGI SARAF
%A AVI WIGDERSON
%T IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
%J Forum of Mathematics, Sigma
%D 2014
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2014.2/
%R 10.1017/fms.2014.2
%G en
%F 10_1017_fms_2014_2
ZEEV DVIR; SHUBHANGI SARAF; AVI WIGDERSON. IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM. Forum of Mathematics, Sigma, Tome 2 (2014). doi: 10.1017/fms.2014.2

Cité par Sources :