TR10-044 Authors: Eli Ben-Sasson, Swastik Kopparty

Publication: 12th March 2010 15:39

Downloads: 1420

Keywords:

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq \F_p^n$ of dimension

at least $d$. For dispersers, ``pseudorandom behavior'' means that $f$ is nonconstant over $S$, i.e., $\left|\{f(s) \mid s\in S\}\right|>1$. For extractors, it means that $f(s)$ is distributed almost uniformly over $\mathbb F_p$ when $s$ is distributed uniformly over $S$.

Dispersers and extractors for affine sources have been considered in the context of deterministic

extraction of randomness from structured sources of imperfect

randomness. Previously, explicit

constructions of affine dispersers were known for every $d = \Omega(n)$,

due to Barak, Kindler, Shaltiel, Sudakov and Wigderson (2005) and explicit affine extractors for the same dimension were obtained by Bourgain (2007).

The main result of this paper is an efficient deterministic construction of affine dispersers for {\em sublinear}

dimension $d = \Omega(n^{4/5})$. Additional results include a new and simple affine extractor for dimension $d>2n/5$,

and a simple disperser for multiple independent affine sources.

The main novelty in this paper lies in the method of proof,

which makes use of classical algebraic objects called

{\em subspace polynomials}.

In contrast, the papers mentioned above relied on

the sum-product theorem for finite fields and other recent results

from additive combinatorics.