An (n, k)-bit-fixing source is a distribution X over {0, 1}n such that there is a subset of k variables in X1, . . .,Xn 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, 1}^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²/n) bits, and requires k > \sqrt 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 ≫ \sqrt n the extracted bits have statistical distance 2^{ - n^{\Omega (1)} } from uniform, and for k ≤ \sqrt n the extracted bits have statistical distance k^{ - \Omega (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.