Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-108 | 28th September 2005 00:00

Deterministic Extractors for Affine Sources over Large Fields

RSS-Feed




TR05-108
Authors: Ariel Gabizon, Ran Raz
Publication: 29th September 2005 19:19
Downloads: 3882
Keywords: 


Abstract:

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 {\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$.



ISSN 1433-8092 | Imprint