Re:Elegant six-page proof reveals the emergence of random st...
by limoce on Tuesday April 26, 2022 @03:29AM
(#31164924)
Cuckoo hash must be a great example. I was interested in the problem solved by this paper solely because I learnt the analysis of time complexity of cuckoo hash just a few months ago.
The puzzle instances are pseudo-random graphs in which edges are defined by the siphash24 hash function, and the solutions are cycles of length L, which have a chance of about 1/L of occurring.
[1] https://github.com/tromp/cuckoo