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 >>>

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly distributed and independent of each other, and the remaining $n-k$ variables are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n \ar \B^m$ which on an ... more >>>

An $(n,k)$-affine source over a finite field $F$ is a random variable $X=(X_1,...,X_n) \in F^n$, which is uniformly distributed over an (unknown) $k$-dimensional affine subspace of $ F^n$. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than $n^c$ (where ... more >>>