Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SYLVESTER-GALLAI:
Reports tagged with Sylvester-Gallai:
TR10-013 | 31st January 2010

#### From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

Revisions: 1

We study the problem of identity testing for depth-3 circuits, over the
field of reals, of top fanin k and degree d (called sps(k,d)
identities). We give a new structure theorem for such identities and improve
the known deterministic d^{k^k}-time black-box identity test (Kayal &
Saraf, FOCS 2009) to one ... more >>>

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

TR12-139 | 2nd November 2012
Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

#### Sylvester-Gallai type theorems for approximate collinearity

We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of ... more >>>

TR22-037 | 10th March 2022
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

More precisely, given a parameter $0 < \delta \leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a ... more >>>