Geometric problems arising in theoretical computer science

-
Zeev Dvir, Princeton University
Fine Hall 314

In this talk I will demonstrate two cases where basic geometric questions, regarding intersections of lines, come up in theoretical computer science. In the first part of the talk I will discuss the finite field kakeya problem. This is a problem regarding intersections of lines in different directions which originated in real analysis and arose independently in computer science in relation to explicit constructions of certain pseudo-random graphs. In the second part of the talk I will discuss certain robust generalizations of the Sylvester-Gallai theorem. In these type of problems, combinatorial information about intersections of lines is transformed into dimension bounds. These type of questions come up in computer science when studying properties of special families of error-correcting codes. In both of these cases tools (mostly algebraic) and intuitions from theoretical computer science have proven to be quite useful in making progress.