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 points must be collinear. Thus basically the result shows that many `local' linear dependencies implies a `global' bound on the dimension of the entire set of points. Variations of these questions have been well studied in additive combinatorics and incidence geometry. In the last few years, techniques from these areas have proven to be very useful in several structural results in theoretical computer science. In this talk I will describe several extensions to the Sylvester-Gallai theorem - quantitative versions, approximate versions and high dimensional versions. We will see connections of these results to rank bounds for design matrices. I will also survey some connections of these incidence theorems to show new and strengthened lower bounds for locally correctable codes over the reals.
Based on joint works with Albert Ai, Zeev Dvir and Avi Wigderson
Copyright. All Rights Reserved.