Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity

For every finite set of points in the plane, if every line going through any two of them contains a third, then they all lie on a single line. This ``local-to-global" theorem (which you can play with proving)  has many generalizations, to higher dimensions, colored points, different fields and more.

In this talk, we'll discuss quantitative versions of such theorems (in which "sufficiently many" local conditions still imply global structure). We'll see that motivations for such natural discrete geometry results arise from various areas in complexity theory, including locally correctable codes, polynomial identity testing and matrix rigidity.

Proofs of these theorems follow an independently intersting result, providing sharp lower bounds on the rank of large classes of ``design" matrices, specified only by the zero/nonzero pattern of their entries. The elementary proof, which I will give in full, curiously combines combinatroial, algebraic and analytic tools.

Based on (old) joint works with Boaz Barak, Zeev Dvir, Shubhangi Saraf and Amir Yehudayoff. No special background is assumed.