Deterministic extractors for affine sources over large fields

An (n, k) -affine source over a finite field double-struck F sign is a random variable X = (X₁,..., X_n) ∈ double-struck F signⁿ, which is uniformly distributed over an (unknown) k-dimensional affine subspace of double-struck F signⁿ. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than n^c (where c is a large enough constant). Our main results are as follows: 1. (For arbitrary k): For any n, k and any double-struck F sign of size larger than n²⁰, we give an explicit construction for a function D : double-struck F signⁿ → double-struck F sign^k-1, such that for any (n, k)-affine source X over double-struck F sign, the distribution of D(X) is ε-close to uniform, where ε is polynomially small in |double-struck F sign|. 2. (For k = 1): For any n and any double-struck F sign of size larger than n^c, we give an explicit construction for a function D : double-struck F sign ⁿ → {0, 1}^{(1-δ)log2 |double-struck F sign|} such that for any (n, 1)-affine source X over double-struck F sign, the distribution of D(X) is ε-close to uniform, where ε is polynomially small in |double-struck F sign|. Here, δ > 0 is an arbitrary small constant, and c is a constant depending on δ.