Seminar: April 27, 2009

Zeev Dvir, IAS

Recent Progress on Kakeya Sets, Mergers and Extractors

Kakeya sets (in vector spaces over finite fields) are sets that contain a line in every direction. It was conjectured by Wolff in 1999 that every Kakeya set has positive density (its size is a constant fraction of the whole space). This conjecture is motivated by several problems in mathematics and in computer science. In particular, it has a tight connection with explicit constructions of 'extractors' and 'mergers' which are efficient procedures that transform weak sources of randomness into strong ones and have many applications.

In this talk I will show the recent proof of Wolff's conjecture [D. 08], the application of the proof technique to the construction of mergers and extractors [D. Wigderson 08] and a new work [D. Kopparty Sudan Saraf 09] that extends the methods in earlier papers to derive near optimal bounds on Kakeya sets and mergers.