Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Incidence Geometry, Rank Bounds for Design Matrices, and Applications
event speaker icon
Shubhangi Saraf (Rutgers University)
event date icon
Wednesday, 17.05.2017, 12:30
event location icon
Taub 201
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 areas such as arithmetic complexity as well as coding theory.

In this talk I will survey some of these connections as well as highlight some of the proof techniques (such as rank bounds for design matrices). I will also talk about a recent result which gives a linear lower bound for the number of ordinary lines (lines through exactly two points) determined by a point set spanning 3 dimensional complex space.

Based on joint works with Abdul Basit, Zeev Dvir, Neeraj Kayal, Avi Wigderson and Charles