On 11/17/2013 02:14 PM, Ivan Kazmenko wrote:
On Sunday, 17 November 2013 at 13:07:40 UTC, Timon Gehr wrote:
On 11/17/2013 02:07 AM, Ivan Kazmenko wrote:
The random pick fails in the following sense: if we seed the RNG,
construct a killer case, and then start with the same seed, we get
Theta(n^2) behavior reproduced.
Hence, in no sense. This does not perform independent uniform random
picks.
Not at all. There is a number of situations where you want your program
to use RNG, but it is also important for the result to be reproducible.
In such cases, you typically store the RNG seed for re-use.
Of course there are also many cases where you don't need reproducibility
guarantees, and there, the attack is useless.
Ivan Kazmenko.
One can't say random picking is bad because one can use some other
(deterministic) pivot selection algorithm instead which is bad. If you
need deterministic reproducibility guarantees, then random picking is
useless.
