Revision #2 Authors: Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Accepted on: 19th May 2009 00:00

Downloads: 2970

Keywords:

We extend the ``method of multiplicities''

to get the following

results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item

We show that every Kakeya set (a set of points that

contains a line in every direction) in $\F_q^n$

must be of size at least $q^n/2^n$.

This bound is tight to within a $2 + o(1)$ factor for

every $n$ as $q \to \infty$, compared to previous

bounds that were off by exponential factors in $n$.

\item

We give improved randomness extractors and ``randomness mergers''.

Mergers are seeded functions that take as input $\Lambda$ (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-\delta) \cdot N$ when

one of the $\Lambda$ input variables is distributed uniformly. The

seed we require is only $(1/\delta)\cdot \log \Lambda$-bits long,

which significantly improves upon previous construction of

mergers. \item Using our new mergers, 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.

\end{enumerate}

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 {\em

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 {\em 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

$S^n$, for any finite subset $S$ of the underlying field, is at most

$d/|S|$ (a fact that does not seem to have been noticed in the

CS literature before).

Revision #1 Authors: Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Accepted on: 16th January 2009 00:00

Downloads: 3026

Keywords:

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction. begin{enumerate} item We show that every Kakeya set in $F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight to within a $2 + o(1)$ factor for every $n$ as $q to infty$. item We give improved ``randomness mergers'', i.e., seeded functions that take as input $k$ (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-delta) cdot N$ when one of the $k$ input variables is distributed uniformly. The seed we require is only $(1/delta)cdot log k$-bits long, which significantly improves upon previous construction of mergers. end{enumerate} 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 {em 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 {em with high multiplicity} outside the set. This novelty leads to significantly tighter analyses. To get 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 $S^n$, for any finite subset $S$ of the underlying field, is at most $d/|S|$ (a fact that does not seem to have been noticed in the CS literature before).

TR09-004 Authors: Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Publication: 15th January 2009 14:51

Downloads: 2954

Keywords:

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight to within a $2 + o(1)$ factor for every $n$ as $q \to \infty$.

\item We give improved ``randomness mergers'', i.e., seeded functions that take as input $k$ (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-\delta) \cdot N$ when one of the $k$ input variables is distributed uniformly. The seed we require is only $(1/\delta)\cdot \log k$-bits long, which significantly improves upon previous construction of mergers.

\end{enumerate}

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 {\em 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 {\em with high multiplicity} outside the set. This novelty leads to significantly tighter analyses.

To get 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 $S^n$, for any finite subset $S$ of the underlying field, is at most $d/|S|$ (a fact that does not seem to have been noticed in the CS literature before).