<p>My goal is to understand well a paper like <a href="http://www.cs.toronto.edu/%7Efbacchus/csc2512/Readings/Meel_Counting_Overview.pdf" rel="nofollow noreferrer">ApproxMC</a>. 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.</p>
<p>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.</p>
<p>Other similar problems in my understanding is LSH (Locality Sensitive Hashing).</p>

CC BY-SA 4.0
2021-03-23T14:27:27.417Z
Try Jeff Erickson's notes for hashing. https://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. https://courses.engr.illinois.edu/cs498abd/fa2020/schedule.html
Chandra Chekuri
CC BY-SA 4.0
2021-03-24T19:21:50.737Z
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.
D.W.
<randomized-algorithms><hash-function>
Reference Request : Accessible reference for Randomised algorithms and Hashing for non-Computer Scientists?
SagarM
# Reference Request : Accessible reference for Randomised algorithms and Hashing for non-Computer Scientists?

(Asked by: username_0 on 2021-03-23)

My goal is to understand well a paper like [ApproxMC](http://www.cs.toronto.edu/%7Efbacchus/csc2512/Readings/Meel_Counting_Overview.pdf). 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).

**Tags:** randomized-algorithms, hash-function

> **Comments:**
> **username_1**: Try Jeff Erickson's notes for hashing. https://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. https://courses.engr.illinois.edu/cs498abd/fa2020/schedule.html  
> **username_2**: 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.  

---

## 0 answers

