Document Open Access Logo

Deterministic Coupon Collection and Better Strong Dispersers

Authors Raghu Meka, Omer Reingold, Yuan Zhou

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.872.pdf
  • Filesize: 0.48 MB
  • 13 pages

Document Identifiers

Author Details

Raghu Meka
Omer Reingold
Yuan Zhou

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.872

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.

Subject Classification

Keywords
  • Coupon collection; dispersers
  • strong dispersers
  • hashing
  • pseudorandomness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 132-140. ACM, 1987. Google Scholar
  2. Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, and Gábor Tardos. Linear hash functions. J. ACM, 46(5):667-683, 1999. Google Scholar
  3. Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 1-10, 2005. Google Scholar
  4. Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson. 2-source dispersers for sub-polynomial entropy and ramsey graphs beating the frankl-wilson construction. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 671-680, 2006. Google Scholar
  5. Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pages 40-47, 2010. Google Scholar
  6. J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. Journal of computer and system sciences, 18(2):143-154, 1979. Google Scholar
  7. L Elisa Celis, Omer Reingold, Gil Segev, and Udi Wieder. Balls and bins: Smaller hash families and faster evaluation. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 599-608. IEEE, 2011. Google Scholar
  8. Benny Chor and Oded Goldreich. On the power of two-point based sampling. J. Complexity, 5(1):96-106, 1989. Google Scholar
  9. Yevgeniy Dodis, Amit Sahai, and Adam Smith. On perfect and adaptive security in exposure-resilient cryptography. In EUROCRYPT, pages 301-324, 2001. Google Scholar
  10. Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, and Madhu Sudan. Extensions to the method of multiplicities, with applications to kakeya sets and mergers. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 181-190, 2009. Google Scholar
  11. Ariel Gabizon, Ran Raz, and Ronen Shaltiel. Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J. Comput., 36(4):1072-1094, 2006. Google Scholar
  12. Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, and David Zuckerman. Security preserving amplification of hardness. In Proceedings of the 31th Annual IEEE Symposium on Foundations of Computer Science, pages 318-326. IEEE, 1990. Google Scholar
  13. Ronen Gradwohl, Guy Kindler, Omer Reingold, and Amnon Ta-Shma. On the error parameter of dispersers. Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, pages 294-305, 2005. Google Scholar
  14. Venkatesan Guruswami, Christopher Umans, and Salil Vadhan. Unbalanced expanders and randomness extractors from parvaresh-vardy codes. Journal of the ACM (JACM), 56(4):20, 2009. Google Scholar
  15. Alexander D Healy. Randomness-efficient sampling within NC1. Computational Complexity, 17(1):3-37, 2008. Google Scholar
  16. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bull. of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  17. Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography. SIAM J. Comput., 36(5):1231-1247, 2007. Google Scholar
  18. A Lubotzky, R Phillips, and P Sarnak. Explicit expanders and the ramanujan conjectures. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 240-246. ACM, 1986. Google Scholar
  19. Joseph Naor and Moni Naor. Small-bias probability spaces: efficient constructions and applications. SIAM Journal on Computing, 22(4):838-856, 1993. Google Scholar
  20. Noam Nisan and David Zuckerman. Randomness is linear in space. J. Comput. Syst. Sci., 52(1):43-52, 1996. Google Scholar
  21. Jaikumar Radhakrishnan and Amnon Ta-Shma. Tight bounds for depth-two superconcentrators. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 585-594. IEEE, 1997. Google Scholar
  22. Anup Rao. Extractors for a constant number of polynomially small min-entropy independent sources. SIAM Journal on Computing, 39(1):168-194, 2009. Google Scholar
  23. Ran Raz, Omer Reingold, and Salil P. Vadhan. Error reduction for extractors. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 191-201, 1999. Google Scholar
  24. Omer Reingold, Ronen Shaltiel, and Avi Wigderson. Extracting randomness via repeated condensing. SIAM Journal on Computing, 35(5):1185-1209, 2006. Google Scholar
  25. Aravind Srinivasan and David Zuckerman. Computing with very weak random sources. SIAM Journal on Computing, 28(4):1433-1459, 1999. Google Scholar
  26. Amnon Ta-Shma, Christopher Umans, and David Zuckerman. Loss-less condensers, unbalanced expanders, and extractors. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing, pages 143-152. ACM, 2001. Google Scholar
  27. Amnon Ta-Shma and David Zuckerman. Extractor codes. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing, pages 193-199, 2001. Google Scholar
  28. Salil Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact