News for hackers. Stuff that matters.
Re:Elegant six-page proof reveals the emergence of random st... by tromp on Tuesday April 26, 2022 @02:56AM (#31164756)
This is exactly what the Cuckoo Cycle [1] family of graph-theory Proof-of-Work systems gets its name from.

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

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.