Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity

This lecture from the Computer Science/Discrete Mathematics Seminar II features Avi Wigderson from the Institute for Advanced Study exploring the fascinating intersection of discrete geometry and computational complexity. Delve into "local-to-global" theorems starting with Sylvester-Gallai's fundamental result: when every line through any two points in a finite planar set contains a third point, all points must lie on a single line. Discover quantitative versions of these theorems and their applications in complexity theory, including locally correctable codes, polynomial identity testing, and matrix rigidity. The presentation includes complete proofs of sharp lower bounds on the rank of "design" matrices using a unique combination of combinatorial, algebraic, and analytic tools. Based on joint works with Boaz Barak, Zeev Dvir, Shubhangi Saraf, and Amir Yehudayoff, this 1-hour 53-minute talk requires no special background knowledge.