Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 30, 2020, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Saeed Ilchi
In this talk, we study the maximum loads of explicit hash families in the d-choice schemes when allocating sequentially n balls into n bins. We consider the Uniform-Greedy scheme which provides d independent bins for each ball and places the ball into the bin with the least load. We construct a hash family with O(log n log log n) random bits. The maximum loads of our hash family match the maximum loads of a perfectly random hash function in the Uniform-Greedy scheme, up to the low order term of constants. Previously, the best known hash families matching the same maximum loads of a perfectly random hash function in d-choice schemes were O(log n)-wise independent functions, which needs O(log2 n) random bits. This talk is based on .
 Chen, Xue. "Derandomized balanced allocation." Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2019.
Automatic MiSe System Software Version 1.4803M | admin login