首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Sylvester-Gallai type theorems for approximate collinearity
  • 本地全文:下载
  • 作者:Albert Ai ; Zeev Dvir ; Shubhangi Saraf
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 approximately collinear triples in a set of points in d dimensional complex space 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 2 queries

  • 关键词:Locally Correctable Code; Reals; Sylvester-Gallai
国家哲学社会科学文献中心版权所有