Ariel Gabizon, Ran Raz

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

Eli Ben-Sasson, Ariel Gabizon

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>