Extractors using hardness amplification

Anindya De*, Luca Trevisan

*Corresponding author for this work

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

3 Scopus citations

Abstract

Zimand [24] presented simple constructions of locally computable strong extractors whose analysis relies on the direct product theorem for one-way functions and on the Blum-Micali-Yao generator. For N-bit sources of entropy γN, his extractor has seed O(log2 N) and extracts N γ/3 random bits. We show that his construction can be analyzed based solely on the direct product theorem for general functions. Using the direct product theorem of Impagliazzo et al. [6], we show that Zimand's construction can extract Ωγ(N1/3) random bits. (As in Zimand's construction, the seed length is O(log2 N) bits.) We also show that a simplified construction can be analyzed based solely on the XOR lemma. Using Levin's proof of the XOR lemma [8], we provide an alternative simpler construction of a locally computable extractor with seed length O(log2 N) and output length Ωγ(N 1/3). Finally, we show that the derandomized direct product theorem of Impagliazzo and Wigderson [7] can be used to derive a locally computable extractor construction with O(logN) seed length and Ω(N1/5) output length. Zimand describes a construction with O(logN) seed length and O(2√log N) output length.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings
Pages462-475
Number of pages14
DOIs
StatePublished - Nov 6 2009
Event12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 - Berkeley, CA, United States
Duration: Aug 21 2009Aug 23 2009

Publication series

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

Other

Other12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009
CountryUnited States
CityBerkeley, CA
Period8/21/098/23/09

Keywords

  • Direct product theorems
  • Extractors
  • Hardness amplification

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Extractors using hardness amplification'. Together they form a unique fingerprint.

  • Cite this

    De, A., & Trevisan, L. (2009). Extractors using hardness amplification. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings (pp. 462-475). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5687 LNCS). https://doi.org/10.1007/978-3-642-03685-9_35