### DIMACS Theoretical Computer Science Seminar

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

See: http://paul.rutgers.edu/~yixinxu/theory-fall12.html