Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Udi Wieder:

TR11-068 | 27th April 2011
L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

Balls and Bins: Smaller Hash Families and Faster Evaluation

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

ISSN 1433-8092 | Imprint