3 ms·
That would fix the final independence problem, but it would also require further changes to other stages of the proof. For example, this strategy would then me
by gopiandcode 6y ago
That would fix the final independence problem, but it would also require further changes to other stages of the proof.
For example, this strategy would then mean that when calculating the probability of a single bit being set, the hash outcomes are no longer independent, which means that a different expression would be needed.
Additionally, from a practical sense, this variation might also be more costly to execute, as setting bits would go from a single memory access to a linear scan.
I think it might be interesting to look into though.
- anonymoushn 6y agoYou can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.