Title: Rank bound for design matrices and applications to incidence theorems and locally correctable codes
Speaker: Shubhangi Saraf, Rutgers University
Date: Wednesday, October 24, 2012 11:00-12:00pm
Location: CoRE Bldg, Room 301, CoRE A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Consider a finite set of points in R^n. The classical theorem of Sylvester-Gallai says that, if for every two points there is a third point on the line through them, then all points are on the same line. In this talk I will describe several extensions to this theorem - quantitative versions, high dimensional versions, and average case versions. The main component of our proofs is an improved lower bound on the rank of design matrices, which are matrices over the complexes with certain zero-nonzero patterns. We use our improved lower bounds on the rank to get improved analyses for several questions in incidence geometry. These results build upon and extend a recent work of Barak, Dvir, Wigderson and Yehudayoff.
I will also talk about stable versions of the Sylvester-Gallai Theorem, where we are only guaranteed many triples of points which are approximately collinear. Configurations with many approximately collinear q-tuples of points also arise naturally in stable versions of Locally Correctable Codes over the complex numbers. We show that that such stable codes with constant query complexity do not exist. No impossibility results were known in any such local setting for more than 2 queries.
Based on joint works with Albert Ai, Zeev Dvir and Avi Wigderson