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