My goal is to understand well a paper like ApproxMC. It discusses the use of Hash functions for Propositional Model Counting. In my understanding what they call hash functions are just random XOR's added to propositional formulas. On the other hand any tutorial level discussion on hashing is completely dedicated to putting data in bins for easy access which seems completely divorced from their discussion.

I would like to have a reference on randomised algorithms, which is able to explain universal hashing from scratch and is able to build up to the level of rigorous statistical understanding of universal hashing families.

Other similar problems in my understanding is LSH (Locality Sensitive Hashing).

  • 1
    $\begingroup$ Try Jeff Erickson's notes for hashing. jeffe.cs.illinois.edu/teaching/algorithms/notes/05-hashing.pdf. You can look at various places for LSH. I teach it in my course on big data algorithms. Slides and videos and references may be helpful to you. courses.engr.illinois.edu/cs498abd/fa2020/schedule.html $\endgroup$ Mar 23, 2021 at 14:27
  • 1
    $\begingroup$ This doesn't seem like a research-level question to me. There are many sources of information on universal hashing, which you should be able to find with a little bit of searching (Wikipedia even has an article on it, and I expect it to be covered in many standard textbooks). Also, please ask about only one thing. LSH is separate. $\endgroup$
    – D.W.
    Mar 24, 2021 at 19:21


Your Answer

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

Browse other questions tagged or ask your own question.