To have 50% odds of at least one L-cycle edge, you need to sample about 1.5%
log(n) doesn't cut it.
To quote myself back: "Not guaranteed, but ... can always start over." In other words, you can settle for a 20% chance if you're willing to run the sampling test a few times, if it saves you enough memory.
That's why I mentioned 50%. Settling for 20% or 50% makes little difference.
You can settle for 0.1% and still the log(n) doesn't cut it.
The definition of the problem is to find a cycle, not the cycle.
Again, this makes no difference except for small constant factors, since you expect to
find about only 3 cycles on average.
Your writeup of Cuckoo Cycle, as of Mar 28 09:28, said:
"We introduce the very first proof-of-work system that is both verify-trivial and tmto-hard."
Period. There were no qualifiers attached to that statement. No conjectures, no conditionals, until section 10, where you note that it's a conjecture.
Yes - if you said "We introduce the first Proof-of-Work scheme based upon graph-theoretical structures. We hypothesize but have not proved that this PoW may lead to certain memory-hardness properties" I'd be totally fine with it, because it would be an accurate description of what you've done.
You're right. I was wrong to claim hardness without proof.
I rewrote the README and shall rewrite the paper as well when I have time,
possibly dropping the hardness hypothesis.
Create a bitvector representing the first half of the nonces. Call it the "lower half".
Iterate on this bitvector using the full nonce state *multiple times* until you have eliminated all candidates in the "lower half" bitvector that you can relative to the full set of candidates in the lower half (some of which are being eliminated) and all candidate nonces in the "upper half" (which you're not eliminating because you don't have memory).
Then, in piecewise fashion, identify a size-appropriate subset of the specific incident edges on the lower half that are causing problems -- in other words, which nonces in the "upper half" are causing collisions in the "lower half" that prevent you from discarding some of the lower-half entries?
For that small subset (of size << 1/2N -- let's say 1/8th N), do the same process: Eliminate them relative to your now-sparsified lower half and the complete upper half. This should allow you to eliminate more of the lower-half edges. Repeat until the lower-half is sufficiently sparse that you can represent it in reasonable compressed space, and move on to the upper half.
Thanks for elaborating on how to pass the incompressibility threshold.
Rephrasing, you paint half the edges red and half blue, and eliminate red leaf-edges.
Now remaining red edges are separated from the leaves by blue edges.
So you identify a small fraction of these separating blue edges that touch a remaining red edge,
and paint them purple. Identifying some leaf purple edges let's you eliminate some
more green edges. Choose different red edges to paint purple and repeat.
If necessary, try to identify blue edges separated by two red edges from a leaf
by recursing deeper.
