3
$\begingroup$

The article here says below, about a universal hashing technique based on matrix multiplications.

"However, there is a little known method based on using a random matrix. It has lots of advantages - it's a universal family"

I tried to hard to find the source paper of the same to dig deeper but could not. Any references about the technique ?

$\endgroup$
  • 1
    $\begingroup$ Proving \epsilon-universality of random matrix hashing sounds an execise. I once found proofs in Shoup's textbook. $\endgroup$ – xagawa Jul 24 '14 at 12:29
  • $\begingroup$ The method is described in CMU's Lecture 10 notes on hashing: cs.cmu.edu/~avrim/451f11/lectures/lect1004.pdf $\endgroup$ – Joseph Garvin Oct 31 '16 at 14:08
3
$\begingroup$

The source of this result, although it can be found in many other places, is the Wegman-Carter paper 'Universal classes of hash functions'. More specifically, Proposition 9 in page 151.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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