### DIMACS Theoretical Computer Science Seminar

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).