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