Deterministic coupon collection and better strong dispersers

Raghu Meka, Omer Reingold, Yuan Zhou

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

Abstract

Hashing is one of the main techniques in data processing and algorithm design for very large data sets. While random hash functions satisfy most desirable properties, it is often too expensive to store a fully random hash function. Motivated by this, much attention has been given to designing small families of hash functions suitable for various applications. In this work, we study the question of designing space-efficient hash families H = {h : [U] → [N]} with the natural property of covering: H is said to be covering if any set of Ω(N logN) distinct items from the universe (the coupon-collector limit) are hashed to cover all N bins by most hash functions in H. We give an explicit family H of size poly(N) (which is optimal), so that hash functions in H can be specified efficiently by O(logN) bits. We build covering hash functions by drawing a connection to dispersers, which are quite well studied and have a variety of applications themselves. We in fact need strong dispersers and we give new constructions of strong dispersers which may be of independent interest. Specifically, we construct strong dispersers with optimal entropy loss in the high min-entropy, but very small error (poly(n)/2n for n bit sources) regimes. We also provide a strong disperser construction with constant error but for any min-entropy. Our constructions achieve these by using part of the source to replace seed from previous non-strong constructions in surprising ways. In doing so, we take two of the few constructions of dispersers with parameters better than known extractors and make them strong.

Original languageEnglish (US)
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
EditorsKlaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages872-884
Number of pages13
ISBN (Electronic)9783939897743
DOIs
StatePublished - Sep 1 2014
Externally publishedYes
Event17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain
Duration: Sep 4 2014Sep 6 2014

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume28
ISSN (Print)1868-8969

Conference

Conference17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
CountrySpain
CityBarcelona
Period9/4/149/6/14

Keywords

  • Coupon collection
  • Dispersers
  • Hashing
  • Pseudorandomness
  • Strong dispersers

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Deterministic coupon collection and better strong dispersers'. Together they form a unique fingerprint.

  • Cite this

    Meka, R., Reingold, O., & Zhou, Y. (2014). Deterministic coupon collection and better strong dispersers. In K. Jansen, C. Moore, N. R. Devanur, & J. D. P. Rolim (Eds.), Leibniz International Proceedings in Informatics, LIPIcs (pp. 872-884). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 28). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.872