Abstract
An (n, k)-bit-fixing source is a distribution X over {0,1} n such that there is a subset of k variables in X 1,..., X n which are uniformly distributed and independent of each other, and the remaining n - k variables are fixed. A deterministic bit-fixing source extractor is a function E: {0, 1} n → {0, l} m which on an arbitrary (n, k)-bit-fixing source outputs m bits that are statistically-close to uniform. Recently, Kamp and Zuckerman [13] gave a construction of deterministic bit-fixing source extractor that extracts Ω(k 2/n) bits, and requires k > √n. In this paper we give constructions of deterministic bit-fixing source extractors that extract (1 - o(1))k bits whenever k > (log n) c for some universal constant c > 0. Thus, our constructions extract almost all the randomness from bit-fixing sources and work even when k is small. For k ≫ √n the extracted bits have statistical distance 2 -nΩ(1) from uniform, and for k ≤ √n the extracted bits have statistical distance k -Ω(1) from uniform. Our technique gives a general method to transform deterministic bit-fixing source extractors that extract few bits into extractors which extract almost all the bits.
Original language | English (US) |
---|---|
Pages (from-to) | 394-403 |
Number of pages | 10 |
Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
State | Published - 2004 |
Externally published | Yes |
Event | Proceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy Duration: Oct 17 2004 → Oct 19 2004 |
All Science Journal Classification (ASJC) codes
- General Engineering