
Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity
Avi Wigderson, a permanent faculty member at the Institute for Advanced Study, lectures on the Sylvester-Gallai theorem: if every line through two points in a finite planar set contains a third point, then all the points lie on one line. He surveys generalizations of this local-to-global result to higher dimensions, colored points, and other fields, then turns to quantitative versions where approximate local conditions still force global structure. Wigderson connects these discrete geometry questions to complexity theory, including locally correctable codes, polynomial identity testing, and matrix rigidity, and gives a full elementary proof built on rank lower bounds for design matrices defined only by their zero and nonzero entry patterns. The proof mixes combinatorial, algebraic, and analytic techniques. Drawing on joint work with Boaz Barak, Zeev Dvir, Shubhangi Saraf, and Amir Yehudayoff, the talk assumes no special background and runs just under two hours as part of the IAS Computer Science and Discrete Mathematics seminar series.