The set reconciliation problem asks two parties to "reconcile" the difference between two sets they each hold. Invertible Bloom Lookup Tables give an excellent solution to this problem, and their analysis dives deep into random hypergraphs, iterated functions, and fixed points.
Readings
- Michael Goodrich and Michael Mitzenmacher. Invertible Bloom Lookup Tables.
- Martin Dietzfelbinger et al. Tight Bounds for Cuckoo Hashing via XORSAT.
Links