Title: The finite field Kakeya conjecture and applications to the construction of mergers and extractors.
Speaker: Zeev Dvir, the Weizmann Institute of Science
Date: Wednesday, September 17, 2008 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
A Kakeya set in F^n, where F is a finite field, is a set containing a line in every direction. The finite field Kakeya conjecture states that the size of such sets is bounded from below by C_n*|F|^n, where C_n depends only on the dimension n.
The interest in this problem came first from Mathematics as a finite field analog of the famous Euclidean Kakeya problem and later from Computer Science as a problem related to explicit constructions of mergers and extractors.
I will talk about the recent proof of this conjecture (Dvir 2008) and its application to the construction of mergers and extractors (Dvir & Wigderson 2008).