Suggested Final Project Topics

Why it’s worth studying:  In one sense, the CR-precis is familiar territory: it’s literally a count-min

sketch with a deterministic choice of hash functions. In another, it’s a whole different world from the

count-min sketch, since it has to somehow get all the benefits typically associated with randomization in a

totally deterministic way. The math powering the CR-precis is beautiful and would be a great launching

point for further exploration of the field of derandomization.

---

 18 / 22

Locality-Sensitive Hashing

A locality-sensitive hash function is a hash function that, counterintuitively, attempts to make similar ele-

ments collide with one another. The idea is that elements that are close to one another in some space

should have a high probability of a hash collision, while elements that are far apart should be kept sepa-

rate. This can be used to do nearest-neighbor searching and as a subroutine in a huge number of modern

algorithms.