Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with design matrix:
TR12-138 | 2nd November 2012
Zeev Dvir, Shubhangi Saraf, Avi Wigderson

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

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 ... more >>>

ISSN 1433-8092 | Imprint