Tight Bounds for Hashing Block Sources

DOI10.1007/978-3-540-85363-3_29zbMATH Open1159.68637arXiv0806.1948OpenAlexW2119574607MaRDI QIDQ3541807

Publication date: 27 November 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: It is known that if a 2-universal hash function

H

is applied to elements of a {em 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 $2 l o g T$ in previous work to $l o g T$ , 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.

Full work available at URL: https://arxiv.org/abs/0806.1948

Mathematics Subject Classification ID

Randomized algorithms (68W20)