### 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(log^{2} 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 Ω_{γ}(N^{1/3}) random bits. (As in Zimand's construction, the seed length is O(log^{2} 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(log^{2} 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 Ω(N^{1/5}) output length. Zimand describes a construction with O(logN) seed length and O(2^{√log N}) output length.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 12th International Workshop, APPROX 2009 and 13th International Workshop, RANDOM 2009, Proceedings |

Pages | 462-475 |

Number of pages | 14 |

DOIs | |

State | Published - Nov 6 2009 |

Event | 12th 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 2009 → Aug 23 2009 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5687 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009 |
---|---|

Country | United States |

City | Berkeley, CA |

Period | 8/21/09 → 8/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

*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