• Calendar

January 16, Wednesday
12:00 – 14:00

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 $c$ is a large enough constant).

Our main results are as follows: (For arbitrary k): For any n,k and any F of size larger than $n^{20}$, we give an explicit construction for a function $D: F^n \rightarrow F^{k-1}$, such that for any $(n,k)$-affine source X over F, the distribution of $D(X)$ is $\epsilon$-close to uniform, where $\epsilon$ is polynomially small in $|F|$. (For k=1): For any n and any F of size larger than $n^{c}$, we give an explicit construction for a function $D: F^n \rightarrow \{0,1\}^{(1-\delta) \log_2|F|}$, such that for any $(n,1)$-affine source X over F, the distribution of $D(X)$ is $\epsilon$-close to uniform, where $\epsilon$ is polynomially small in $|F|$. Here, $\delta > 0$ is an arbitrary small constant, and $c$ is a constant depending on $\delta$.

Joint work with Ran Raz