Zero-fixing extractors for sub-logarithmic entropy

Gil Cohen, Igor Shinkar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

An (n, k)-bit-fixing source is a distribution on n bit strings, that is fixed on n − k of the coordinates, and jointly uniform on the remaining k bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract (1 − o(1)) ・ k bits for k = poly log n, almost matching the probabilistic argument. Intriguingly, unlike other well-studied sources of randomness, a result of Kamp and Zuckerman [SICOMP 2006] shows that, for any k, some small portion of the entropy in an (n, k)-bit-fixing source can be extracted. Although the extractor does not extract all the entropy, it does extract log(k)/2 bits. In this paper we prove that when the entropy k is small enough compared to n, this exponential entropy-loss is unavoidable. More precisely, we show that forn > Tower(k2) one cannot extract more than log(k)/2+O(1) bits from (n, k)-bit-fixing sources. The remaining entropy is inaccessible, information theoretically. By the Kamp-Zuckerman construction, this negative result is tight. For small enough k, this strengthens a result by Reshef and Vadhan [RSA 2013], who proved a similar bound for extractors computable by space-bounded streaming algorithms. Our impossibility result also holds for what we call zero-fixing sources. These are bit-fixing sources where the fixed bits are set to 0. We complement our negative result, by giving an explicit construction of an (n, k)-zero-fixing extractor that outputs Ω(k) bits for k ≥ poly log log n. Finally, we give a construction of an (n, k)-bit-fixing extractor, that outputs k − O(1) bits, for entropy k = (1 + o(1)) ・ log log n, with running-time nO((log log n)2). This answers an open problem by Reshef and Vadhan [RSA 2013].

Original languageEnglish (US)
Title of host publicationAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
EditorsMagnus M. Halldorsson, Naoki Kobayashi, Bettina Speckmann, Kazuo Iwama
PublisherSpringer Verlag
Pages343-354
Number of pages12
ISBN (Print)9783662476710
DOIs
StatePublished - Jan 1 2015
Event42nd International Colloquium on Automata, Languages and Programming, ICALP 2015 - Kyoto, Japan
Duration: Jul 6 2015Jul 10 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9134
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
CountryJapan
CityKyoto
Period7/6/157/10/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Zero-fixing extractors for sub-logarithmic entropy'. Together they form a unique fingerprint.

  • Cite this

    Cohen, G., & Shinkar, I. (2015). Zero-fixing extractors for sub-logarithmic entropy. In M. M. Halldorsson, N. Kobayashi, B. Speckmann, & K. Iwama (Eds.), Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings (pp. 343-354). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9134). Springer Verlag. https://doi.org/10.1007/978-3-662-47672-7_28