11-09

Geometry and Computation - Classical Problems From a CS Perspective

In this talk I will demonstrate instances where natural CS problems lead to classical problems in mathematics. In particular, to basic problems in geometry involving lines and points in vector spaces. In some cases these are well known open problems and in others new variants of old theorems. We will see how tools from CS are useful in the study of these problems. In the first part I will explain how constructions of Randomness Extractors are related to the Finite Field Kakeya conjecture. In the second part I will show how Locally Correctable Codes lead to generalizations of the Sylvester-Gallai theorem.

Zeev Dvir is currently a postdoc at the department of computer science in Princeton University. He got his Ph.D from the Weizmann Institute in Israel in 2008 under the guidance of Ran Raz and Amir Shpilka. His main field of research is computational complexity, especially circuit complexity, de-randomization and coding theory.