Deterministic extractors for affine sources over large fields

Ariel Gabizon, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations

Abstract

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 δ.

Original languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages407-418
Number of pages12
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Deterministic extractors for affine sources over large fields'. Together they form a unique fingerprint.

  • Cite this

    Gabizon, A., & Raz, R. (2005). Deterministic extractors for affine sources over large fields. In Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 (pp. 407-418). [1530733] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.31