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 ?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Proving \epsilon-universality of random matrix hashing sounds an execise. I once found proofs in Shoup's textbook. $\endgroup$
    – xagawa
    Commented Jul 24, 2014 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
    Commented Oct 31, 2016 at 14:08

1 Answer 1

Reset to default
4
$\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 and acknowledge you have read our privacy policy.

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