Geodesic
SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY
Forum of Mathematics, Sigma, Tome 2 (2014)

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

We study questions in incidence geometry where the precise position of points is ‘blurry’ (for example 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 approximately collinear triples in a set of points in ${\mathbb{C}}^d$ implies that the points are close to a low dimensional affine subspace. This can be viewed as a stable variant of the Sylvester–Gallai theorem and its extensions. Building on the recently found connection between Sylvester–Gallai type theorems and complex locally correctable codes (LCCs), we define the new notion of stable LCCs, in which the (local) correction procedure can also handle small perturbations in the Euclidean metric. We prove that such stable codes with constant query complexity do not exist. No impossibility results were known in any such local setting for more than two queries. 
@article{10_1017_fms_2014_1,
     author = {ALBERT AI and ZEEV DVIR and SHUBHANGI SARAF and AVI WIGDERSON},
     title = {SYLVESTER{\textendash}GALLAI {TYPE} {THEOREMS} {FOR} {APPROXIMATE} {COLLINEARITY}},
     journal = {Forum of Mathematics, Sigma},
     publisher = {mathdoc},
     volume = {2},
     year = {2014},
     doi = {10.1017/fms.2014.1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2014.1/}
}
TY  - JOUR
AU  - ALBERT AI
AU  - ZEEV DVIR
AU  - SHUBHANGI SARAF
AU  - AVI WIGDERSON
TI  - SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY
JO  - Forum of Mathematics, Sigma
PY  - 2014
VL  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2014.1/
DO  - 10.1017/fms.2014.1
LA  - en
ID  - 10_1017_fms_2014_1
ER  - 
%0 Journal Article
%A ALBERT AI
%A ZEEV DVIR
%A SHUBHANGI SARAF
%A AVI WIGDERSON
%T SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY
%J Forum of Mathematics, Sigma
%D 2014
%V 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2014.1/
%R 10.1017/fms.2014.1
%G en
%F 10_1017_fms_2014_1
ALBERT AI; ZEEV DVIR; SHUBHANGI SARAF; AVI WIGDERSON. SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY. Forum of Mathematics, Sigma, Tome 2 (2014). doi: 10.1017/fms.2014.1

Cité par Sources :