Last time we empirically saw that if we have $m$ slots and $n = \alpha m$ items assigned to those slots via $d$ hash functions, then those items can be peeled with probability close to 1 if and only if $\alpha$ is below some limiting constant. However, we didn't discuss why that happened. Today we dive deep into the dynamics of peeling algorithms, touching on some absolutely beautiful concepts from Theoryland in the process.
Readings
- Martin Dietzfelbinger et al. Tight Bounds for Cuckoo Hashing via XORSAT.
Links