@inproceedings{624b0b0f8dc24c9fbde45016995fdddb,
title = "Deterministic coupon collection and better strong dispersers",
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.",
keywords = "Coupon collection, Dispersers, Hashing, Pseudorandomness, Strong dispersers",
author = "Raghu Meka and Omer Reingold and Yuan Zhou",
note = "Publisher Copyright: {\textcopyright} Ragu Meka, Omer Reingold, and Yuan Zhou.; 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 ; Conference date: 04-09-2014 Through 06-09-2014",
year = "2014",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2014.872",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "872--884",
editor = "Klaus Jansen and Cristopher Moore and Devanur, {Nikhil R.} and Rolim, {Jose D. P.}",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",
address = "Germany",
}