Kakeya Sets and Extractors (survey)

by Zeev Dvir.

Oded's comments

Just see the original abstract.

The original abstract

In a series of works, we have been getting strong new bounds on the size of Kakeya sets, and using the same/related proofs to analyze a new family of randomness extractors, that are capable achieving parameters that were previously unknown. Details below. A Kakeya set in F_q^n is a set that contains a line in every direction. A randomness extractor is a function E:{0,1}^n x {0,1}^t -> {0,1}^m that satisfies the condition that if X is a random variable with sufficiently high minentropy, and s is a uniform random variable (independent of X), then E(X,s) is distributed nearly uniformly. Our specific results include
  1. Z. Dvir. On the size of Kakeya sets in finite fields. This work shows that Kakeya sets must have size c_n q^n where c_n is a universal constant independent of q.
  2. Z.Dvir and A. Wigderson. Kakeya sets, new mergers and old extractors. This work constructs a simple ``merger of random sources based on the ideas from [1], and builds alternate extractors that match state-of-the-art constructions.
  3. S. Saraf and M. Sudan. Improved lower bound on the size of Kakeya sets over finite fields. This work improves the lower bound of [1] to q^n/c^n for some constant c independent of q and n.
  4. Z. Dvir, S. Kopparty, S. Saraf and M. Sudan. Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers. This work improves the Kakeya sets bounds in [1], [3] to q^n/2^n (which is within a factor of 2+o(1) of the upper bounds). It also gives improved analysis of the mergers of [2], leading to explicit extractors attaining a new range of parameters.
All the result are held to together by a unifying technique that could be called the polynomial method. Here combinatorial parameters (like the cardinality) of a set S with algebraic properties are bounded by constructing a polynomial P_S that vanishes on S, and then analyzing this polynomial. This leads often to very simple analysis of parameters that were otherwise elusive.

Back to list of Oded's choices.