TY - JOUR

T1 - Deterministic extractors for affine sources over large fields

AU - Gabizon, Ariel

AU - Raz, Ran

N1 - Funding Information:
* Research supported by Israel Science Foundation (ISF) grant. 1 A line is a 1-dimensional affine subspace of Fn.
Copyright:
Copyright 2009 Elsevier B.V., All rights reserved.

PY - 2008/7

Y1 - 2008/7

N2 - An (n,k)-affine source over a finite field F is a random variable X = (X 1,..., X n ) ε Fn which is uniformly distributed over an (unknown) k-dimensional affine subspace of Fn . 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 F of size larger than n 20, we give an explicit construction for a function D Fn → Fk - 1, such that for any (n,k)-affine source X over F, the distribution of D(X) is aŞ-close to uniform, where aŞ is polynomially small in | F |. 2. (For k=1): For any n and any F of size larger than n c , we give an explicit construction for a function D: Fn \to \{ 0,1\} {(1 - \delta )log-2 |F| , such that for any (n, 1)-affine source X over F , the distribution of D(X) is aŞ-close to uniform, where aŞ is polynomially small in | F |. Here, δ>0 is an arbitrary small constant, and c is a constant depending on δ.

AB - An (n,k)-affine source over a finite field F is a random variable X = (X 1,..., X n ) ε Fn which is uniformly distributed over an (unknown) k-dimensional affine subspace of Fn . 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 F of size larger than n 20, we give an explicit construction for a function D Fn → Fk - 1, such that for any (n,k)-affine source X over F, the distribution of D(X) is aŞ-close to uniform, where aŞ is polynomially small in | F |. 2. (For k=1): For any n and any F of size larger than n c , we give an explicit construction for a function D: Fn \to \{ 0,1\} {(1 - \delta )log-2 |F| , such that for any (n, 1)-affine source X over F , the distribution of D(X) is aŞ-close to uniform, where aŞ is polynomially small in | F |. Here, δ>0 is an arbitrary small constant, and c is a constant depending on δ.

UR - http://www.scopus.com/inward/record.url?scp=58549103289&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58549103289&partnerID=8YFLogxK

U2 - 10.1007/s00493-008-2259-3

DO - 10.1007/s00493-008-2259-3

M3 - Article

AN - SCOPUS:58549103289

VL - 28

SP - 415

EP - 440

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 4

ER -