Abstract
The classical Sylvester-Gallai Theorem states the following: given a finite set of points in the Euclidean plane, if the line through every pair of points passes through a third point, then all the points must be collinear. At a high level the result shows that many ``local" linear dependencies implies a ``global" bound on the dimension of the entire set of points. This result has been well studied in mathematics. In recent years variants of the theorem have also found applications to several structural results in theoretical computer science.
In this talk I will describe several extensions to the Sylvester-Gallai theorem - quantitative versions, high dimensional versions, colorful versions and approximate versions. I will also describe some of the applications and connections in theoretical computer science to areas such as polynomial identity testing and local algorithms for error correcting codes.
Based on joint works with Albert Ai, Zeev Dvir, Neeraj Kayal and Avi Wigderson.