Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Albert Ai:

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

ISSN 1433-8092 | Imprint