TY - GEN

T1 - Deterministic extractors for affine sources over large fields

AU - Gabizon, Ariel

AU - Raz, Ran

PY - 2005

Y1 - 2005

N2 - An (n, k) -affine source over a finite field double-struck F sign is a random variable X = (X1,..., Xn) ∈ double-struck F signn, which is uniformly distributed over an (unknown) k-dimensional affine subspace of double-struck F signn. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than nc (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 n20, we give an explicit construction for a function D : double-struck F signn → double-struck F signk-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 nc, we give an explicit construction for a function D : double-struck F sign n → {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 δ.

AB - An (n, k) -affine source over a finite field double-struck F sign is a random variable X = (X1,..., Xn) ∈ double-struck F signn, which is uniformly distributed over an (unknown) k-dimensional affine subspace of double-struck F signn. We show how to (deterministically) extract practically all the randomness from affine sources, for any field of size larger than nc (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 n20, we give an explicit construction for a function D : double-struck F signn → double-struck F signk-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 nc, we give an explicit construction for a function D : double-struck F sign n → {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 δ.

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

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

U2 - 10.1109/SFCS.2005.31

DO - 10.1109/SFCS.2005.31

M3 - Conference contribution

AN - SCOPUS:33748629383

SN - 0769524680

SN - 9780769524689

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 407

EP - 418

BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

T2 - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

Y2 - 23 October 2005 through 25 October 2005

ER -