Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MATT DEVOS:
All reports by Author Matt DeVos:

TR09-063 | 29th July 2009
Matt DeVos, Ariel Gabizon

Simple Affine Extractors using Dimension Expansion

Revisions: 2

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ... more >>>




ISSN 1433-8092 | Imprint