The method of multiplicities
Madhu Sudan
Microsoft/MIT
In 2008, Zeev Dvir achieved a breakthrough in combinatorial
geometry by giving a stunningly simple, and sharp, bound on
the size of "Kakeya Sets" in F_q^n, the n-dimensional vector
space over the finite field on q elements. (A Kakeya set in
any vector space is a set that contains a line in every
direction.) Dvir proved this bound by setting up an n-variate
low-degree non-zero polynomial that vanished on every point in
the set, and then used the algebraic nature of a Kakeya set
to argue that this polynomial was zero too often if the set was
too small. In addition to resolving a long-studied problem in
combinatorial geometry, this method also led to new constructions
of ``randomness extractors''.
In this talk I will describe algebraic methods to improve
the analysis of Dvir, by using polynomials that vanish with
``high multiplicity'' on every point on the given set. This
method, based on prior work with Guruswami (1998), ends up
yielding extremely tight (to within a factor of 2) bounds
on the size of Kakeya sets; and, in combination with a host of
other techniques, state-of-the-art "extractors" (algorithms that
purify randomness).
In this talk I will describe the (simple) idea behind the method
of multiplicities and some of the applications.
Based on joint works with Shubhangi Saraf (Analysis & PDE, 2009);
and with Zeev Dvir, Swastik Kopparty, and Shubhangi Saraf (FOCS 2009).