Deterministic extractors for bit-fixing sources by obtaining an independent seed

Ariel Gabizon, Ran Raz, Ronen Shaltiel

Research output: Contribution to journalArticle

43 Scopus citations

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 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 [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 ω(k2 /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 languageEnglish (US)
Pages (from-to)1072-1094
Number of pages23
JournalSIAM Journal on Computing
Volume36
Issue number4
DOIs
StatePublished - Dec 1 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

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

Fingerprint Dive into the research topics of 'Deterministic extractors for bit-fixing sources by obtaining an independent seed'. Together they form a unique fingerprint.

  • Cite this