Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-044 | 12th March 2010 15:38

Affine Dispersers from Subspace Polynomials


Authors: Eli Ben-Sasson, Swastik Kopparty
Publication: 12th March 2010 15:39
Downloads: 2931


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

ISSN 1433-8092 | Imprint