ECCC-Report TR05-108https://eccc.weizmann.ac.il/report/2005/108Comments and Revisions published for TR05-108en-usThu, 29 Sep 2005 19:19:43 +0300
Paper TR05-108
| Deterministic Extractors for Affine Sources over Large Fields |
Ariel Gabizon,
Ran Raz
https://eccc.weizmann.ac.il/report/2005/108An $(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 {\mathbb
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: {\mathbb 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$.
Thu, 29 Sep 2005 19:19:43 +0300https://eccc.weizmann.ac.il/report/2005/108