Extensions to the method of multiplicities, with applications to Kakeya sets and mergers

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

52 Scopus citations

Abstract

We extend the "method of multiplicities" to get the following results, of interest in combinatorics and randomness extraction. 1) We show that every Kakeya set (a set of points that contains a line in every direction) in Fqn must be of size at least qn/2n. This bound is tight to within a 2 + o(1) factor for every n as q → ∞, compared to previous bounds that were off by exponential factors in n. 2) We give an improved construction of "randomness mergers". Mergers are seeded functions that take as input Δ (possibly correlated) random variables in {0,1}N and a short random seed, and output a single random variable in {0,1}N that is statistically close to having entropy (1 - δ) · N when one of the Δ input variables is distributed uniformly. The seed we require is only (1/δ) · log Δ-bits long, which significantly improves upon previous construction of mergers. 3) We show how to construct randomness extractors that use logarithmic length seeds while extracting 1 - o(1) fraction of the min-entropy of the source. Previous results could extract only a constant fraction of the entropy while maintaining logarithmic seed length. The "method of multiplicities", as used in prior work, analyzed subsets of vector spaces over finite fields by constructing somewhat low degree interpolating polynomials that vanish on every point in the subset with high multiplicity. The typical use of this method involved showing that the interpolating polynomial also vanished on some points outside the subset, and then used simple bounds on the number of zeroes to complete the analysis. Our augmentation to this technique is that we prove, under appropriate conditions, that the interpolating polynomial vanishes with high multiplicity outside the set. This novelty leads to significantly tighter analyses. To develop the extended method of multiplicities we provide a number of basic technical results about multiplicity of zeroes of polynomials that may be of general use. For instance, we strengthen the Schwartz-Zippel lemma to show that the expected multiplicity of zeroes of a non-zero degree d polynomial at a random point in Sn, for any finite subset S of the underlying field, is at most d/|S|.

Original languageEnglish (US)
Title of host publicationProceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009
Pages181-190
Number of pages10
DOIs
StatePublished - Dec 1 2009
Externally publishedYes
Event50th Annual Symposium on Foundations of Computer Science, FOCS 2009 - Atlanta, GA, United States
Duration: Oct 25 2009Oct 27 2009

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other50th Annual Symposium on Foundations of Computer Science, FOCS 2009
CountryUnited States
CityAtlanta, GA
Period10/25/0910/27/09

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Extractors
  • Polynomial method
  • Randomness

Fingerprint Dive into the research topics of 'Extensions to the method of multiplicities, with applications to Kakeya sets and mergers'. Together they form a unique fingerprint.

  • Cite this

    Dvir, Z., Kopparty, S., Saraf, S., & Sudan, M. (2009). Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. In Proceedings - 50th Annual Symposium on Foundations of Computer Science, FOCS 2009 (pp. 181-190). [5438635] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2009.40