1 Search Results for "Zhou, Yuan"

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.872

Deterministic Coupon Collection and Better Strong Dispersers

Authors: Raghu Meka, Omer Reingold, and Yuan Zhou

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

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 Omega(N log N) 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 covering family H of size poly(N) (which is optimal), so that hash functions in H can be specified efficiently by O(log N) 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)/2^n 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.

Cite as

Raghu Meka, Omer Reingold, and Yuan Zhou. Deterministic Coupon Collection and Better Strong Dispersers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 872-884, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{meka_et_al:LIPIcs.APPROX-RANDOM.2014.872,
  author =	{Meka, Raghu and Reingold, Omer and Zhou, Yuan},
  title =	{{Deterministic Coupon Collection and Better Strong Dispersers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{872--884},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.872},
  URN =		{urn:nbn:de:0030-drops-47440},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.872},
  annote =	{Keywords: Coupon collection; dispersers, strong dispersers, hashing, pseudorandomness}
}

Refine by Author
1 Meka, Raghu
1 Reingold, Omer
1 Zhou, Yuan

Refine by Classification

Refine by Keyword
1 Coupon collection; dispersers
1 hashing
1 pseudorandomness
1 strong dispersers

Refine by Type
1 document

Refine by Publication Year
1 2014

1 Search Results for "Zhou, Yuan"

Deterministic Coupon Collection and Better Strong Dispersers

Abstract

Cite as

Thanks for your feedback!

Could not send message