loading...
Deterministic Extractors for Affine Sources over Large Fields
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.3146th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Ariel Gabizon, Weizmann Institute
Ran Raz, Weizmann Institute

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 nc (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:F^n \to F^{k - 1} , such that for any (n,k)- affine source X over F, the distribution of D(X) is \in -close to uniform, where \in is polynomially small in |F|.

2. (For k = 1): For any n and any F of size larger than nc, we give an explicit construction for a function D : D:F^n \to \{ 0,1\} ^{(1 - 8)\log _2 |F|} |, such that for any (n, 1)- affine source X over F, the distribution of D(X) is \in -close to uniform, where \in is polynomially small in |F|. Here, \delta > 0 is an arbitrary small constant, and c is a constant depending on \delta.

Citation:
Ariel Gabizon, Ran Raz, "Deterministic Extractors for Affine Sources over Large Fields," focs, pp.407-418, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.