### Abstract

An (n, k) -affine source over a finite field double-struck F sign is a random variable X = (X_{1},..., X_{n}) ∈ double-struck F sign^{n}, which is uniformly distributed over an (unknown) k-dimensional affine subspace of double-struck F sign^{n}. 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 double-struck F sign of size larger than n^{20}, we give an explicit construction for a function D : double-struck F sign^{n} → double-struck F sign^{k-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 n^{c}, 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 |

Pages | 407-418 |

Number of pages | 12 |

DOIs | |

State | Published - Dec 1 2005 |

Externally published | Yes |

Event | 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States Duration: Oct 23 2005 → Oct 25 2005 |

### Publication series

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

Volume | 2005 |

ISSN (Print) | 0272-5428 |

### Other

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

Country | United States |

City | Pittsburgh, PA |

Period | 10/23/05 → 10/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

*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