Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed

Abstract

An {n, k)-bit-fixing source is a distribution X over {0, 1}/sup n/ such that there is a subset of k variables in X/sub 1/, ..., X/sub 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, l}/sup n/ /spl rarr/ {0, l}/sup m/ which on an arbitrary (n, k)-bit-fixing source outputs m bits that are statistically-close to uniform. Recently, Kamp and Zuckerman (2003) gave a construction of deterministic bit-fixing source extractor that extracts /spl Omega/(k/sup 2//n) bits, and requires k > /spl radic/n. In this paper we give constructions of deterministic bit-fixing source extractors that extract (1 -o(1))k bits whenever k > (log n)/sup 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 /spl Gt/ /spl radic/n the extracted bits have statistical distance 2/sup -n/spl Omega/(1)/ from uniform, and for k /spl les/ /spl radic/n the extracted bits have statistical distance k/sup -/spl 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.