Incidence geometry, rank bounds for design matrices, and applications

1 May
Theory of Computation Seminar
Shubhangi Saraf, Rutgers University
Monday, May 1, 2017 -
1:15pm to 2:15pm
Maxwell Dworkin 223

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 Wolf

 

Speaker Bio: 

Shubhangi is an Assistant Professor in the Department of Mathematics and the Department of Computer Science at Rutgers University. Prior to joining Rutgers, she received her PhD in computer science from the Massachusetts Institute of Technology and spent a year as a postdoctoral researcher in the School of Mathematics at the Institute for Advanced Study in Princeton. Shubhangi’s research is in theoretical computer science and discrete mathematics, with a focus on complexity theory, algebraic computation, error correcting codes, sublinear time algorithmics and discrete geometry.

Contact: 
Carol Harlow