Videos

Incidence Geometry and Applications in Theoretical Computer Science

Presenter
December 7, 2011
Keywords:
  • geometric algorithms
  • discrete geometry
  • applied combinatorics
  • geometry of numbers
  • polynomial identities
MSC:
  • 68W25
  • 68W40
  • 68Wxx
  • 12-xx
  • 16R60
  • 11Hxx
  • 51Exx
Abstract
I will discuss some results on the incidence geometry of points and lines in Euclidean space and some recent surprising connections to Polynomial Identity Testing and constructions of Locally Correctable Codes. The well-known Sylvester-Gallai Theorem states that given a finite set of points in the 2-dimensional Euclidean plane, either the points are all collinear, or else there is a line passing through exactly two of the points. This seemingly innocuous result has had some very interesting consequences. I will survey various generalizations of this result to colorful versions, high dimensional versions, and approximate versions, and show how such theorems shed light on the structure of depth-3 arithmetic circuits and locally correctable codes.