0
$\begingroup$

This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in the affirmative:

Can we give an explicit uniform but only pairwise independent random process for selecting the next bin to put a ball into which gives the expected max load to be $\Theta(\sqrt{n})$ asymptotically?

Imagine we choose the explicit pairwise independent hash function family $h((ax+b) \bmod p) \bmod n)$. It is a straightforward standard exercise to show an upper bound of the following form:

$$P(\text{max number of values hashed to the same value} \geq 1 + \sqrt{2n}) \leq \frac{1}{2}$$

However, can a matching or near matching lower bound be found for the expected max load for this specific hash function family?

$\endgroup$

1 Answer 1

2
$\begingroup$

The hash family you give has expected max load $\tilde{O}(n^{1/3})$, as shown in this recent paper:

Mathias Bæk Tejs Knudsen, "Linear Hashing is Awesome"

$\endgroup$
1
  • $\begingroup$ That's a pretty amazing result! $\endgroup$
    – Simd
    Jan 27, 2018 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.