Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > L. ELISA CELIS:
All reports by Author L. Elisa Celis:

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