46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) Deterministic Extractors for Affine Sources over Large Fields Pittsburgh, Pennsylvania, USA October 23-October 25 ISBN: 0-7695-2468-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.31
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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||