How much independence is required for separate chaining?

Question

If $n$ balls are placed into $n$ bins uniformly at random, the heaviest loaded bin has $O(\lg n/\lg \lg n)$ balls in it with high probability. In "The Power of Simple Tabulation Hashing", Pătraşcu and Thorup mention that "Chernoff-Hoeffding bounds for applications with limited independence" (mirror) shows that this bound on the population of the heaviest loaded bin also holds if the balls are distributed by an $\Omega(\lg n/\lg \lg n)$-independent hash function.

In "Balls and Bins: Smaller Hash Families and Faster Evaluation", Celis et al. note that it is not known if there is a family of hash functions where

1. Hash functions can be represented with $O(\lg n)$ bits of space
2. Hash functions can be evaluated in $O(1)$ time
3. The maximal load is $O(\lg n / \lg \lg n)$ with high probability.

If there is a constant $k$ such that any $k$-independent family suffices for #3, then it the polynomial construction of $k$-independent families would meet #1 and #2.

What bound do we have for the heaviest loaded bin with $k$-independent hashing?

Using Theorem 4.III of "Chernoff-Hoeffding bounds ..." and the union bound, I think I can get a bound of $O(n^{2/k})$ on the weight of the heaviest loaded bin w.h.p.

Can this be brought down to $O(\lg ^c n)$ using other techniques?

Answer 1

Apparently not. "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$".