Abstract
It is known that if a 2-universal hash function H is applied to elements of a block source (X 1,...,X T ), where each item X i has enough min-entropy conditioned on the previous items, then the output distribution (H,H(X 1),...,H(X T )) will be “close” to the uniform distribution. We provide improved bounds on how much min-entropy per item is required for this to hold, both when we ask that the output be close to uniform in statistical distance and when we only ask that it be statistically close to a distribution with small collision probability. In both cases, we reduce the dependence of the min-entropy on the number T of items from 2logT in previous work to logT, which we show to be optimal. This leads to corresponding improvements to the recent results of Mitzenmacher and Vadhan (SODA ‘08) on the analysis of hashing-based algorithms and data structures when the data items come from a block source.
A full version of this paper can be found on [CV08].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bennett, C.H., Brassard, G., Robert, J.-M.: How to reduce your enemy’s information (extended abstract). In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 468–476. Springer, Heidelberg (1986)
Broder, A.Z., Mitzenmacher, M.: Survey: Network applications of bloom filters: A survey. Internet Mathematics 1(4) (2003)
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17(2), 230–261 (1988)
Chung, K.-M., Vadhan, S.: Tight bounds for hashing block sources (2008), http://www.citebase.org/abstract?id=oai:arXiv.org:0806.1948
Gibbs, A.L., Su, F.E.: On choosing and bounding probability metrics. International Statistical Review 70, 419 (2002)
Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, Seattle, Washington, May 15–17, 1989, pp. 12–24 (1989)
Knuth, D.E.: The art of computer programming. Sorting and Searching, vol. 3. Addison-Wesley Longman Publishing Co., Inc, Boston (1998)
Mitzenmacher, M., Vadhan, S.: Why simple hash functions work: Exploiting the entropy in a data stream. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), January 20–22, 2008, pp. 746–755 (2008)
Muthukrishnan, S.: Data streams: algorithms and applications. In: SODA, p. 413 (2003)
Nisan, N., Ta-Shma, A.: Extracting randomness: A survey and new constructions. J. Comput. Syst. Sci. 58(1), 148–173 (1999)
Nisan, N., Zuckerman, D.: Randomness is linear in space. Journal of Computer and System Sciences 52(1), 43–52 (1996)
Radhakrishnan, J., Ta-Shma, A.: Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics 13(1), 2–24 (2000) (electronic)
Reyzin, L.: A note on the statistical difference of small direct products. Technical Report BUCS-TR-2004-032, Boston University Computer Science Department (2004)
Shaltiel, R.: Recent developments in extractors. In: Paun, G., Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science. Algorithms and Complexity, vol. 1. World Scientific, Singapore (2004)
Vadhan, S.: The unified theory of pseudorandomness. SIGACT News 38(3) (September 2007)
Zuckerman, D.: Simulating BPP using a general weak random source. Algorithmica 16(4/5), 367–391 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chung, KM., Vadhan, S. (2008). Tight Bounds for Hashing Block Sources. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds) Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2008 2008. Lecture Notes in Computer Science, vol 5171. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85363-3_29
Download citation
DOI: https://doi.org/10.1007/978-3-540-85363-3_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85362-6
Online ISBN: 978-3-540-85363-3
eBook Packages: Computer ScienceComputer Science (R0)