Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INCIDENCE GEOMETRY:
Reports tagged with Incidence geometry:
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 >>>

TR15-113 | 9th July 2015
Amit Chakrabarti, Tony Wirth

#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Set cover, over a universe of size $n$, may be modelled as a
data-streaming problem, where the $m$ sets that comprise the instance
are to be read one by one. A semi-streaming algorithm is allowed only
$O(n \text{ poly}\{\log n, \log m\})$ space to process this ... more >>>

ISSN 1433-8092 | Imprint