## 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, 1}^{m} which on an arbitrary (n, k)-bit-fixing source outputs m bits that are statistically close to uniform. Recently, Kamp and Zuckerman [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 92-101] gave a construction of a 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) | 1072-1094 |

Number of pages | 23 |

Journal | SIAM Journal on Computing |

Volume | 36 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1 2006 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)
- Mathematics(all)

## Keywords

- Bit-fixing sources
- Derandomization
- Deterministic extractors
- Seed obtainers
- Seeded extractors