Abstract

The Sylvester-Gallai (SG) theorem in discrete geometry asserts that if a finite set of points P has the property that every line through any two of its points intersects the set at a third point, then P must lie on a line. Surprisingly, this theorem, and some variants of it, appear in the analysis of locally correctable codes and, more noticeably, in algebraic program testing (polynomial identity testing). For these questions one often has to study extensions of the original SG problem: the case where there are several sets, or with a robust version of the condition (many "special" lines through each point) or with a higher degree analog of the problem, etc. In this talk I will present the SG theorem and some of its variants, show its relation to the above mentioned computational problems and discuss recent developments regarding higher degree analogs and their applications.