4 ms·

1. I don't think you understand my point (or possibly the adversarial method). 2. Unless you generate an array ahead of time, you haven't broken randomized qui

1. I don't think you understand my point (or possibly the adversarial method). 2. Unless you generate an array ahead of time, you haven't broken randomized quicksort. 3. For an adversary to have the ability to generate elements on the fly, he must have knowledge of the array, which requires the array to be generated deterministically. 4. The purpose of a randomized algorithm is to prevent the adversary from choosing elements on the fly and forcing the worst case every time. Putting these all together, for McIlroy's adversary to have broken randomized quicksort would be claiming that randomization is useless. We all know this is false.

sesqu 16y ago
Stop thinking about arrays. Think ordered relations. Think collections and comparators. The sort is vulnerable to an attack at the highest abstraction level, where only necessary conditions are used. The usual implementation, using arrays of integers, is not similarly vulnerable. I'm not a fan of randomized algorithms, incidentally. It's selling your best case upriver to ward off offensive poisoning, and adds a multiplier to running time. Still, if you're offline, memory-restricted, timesharing and public-facing, I guess randomized quicksort's better than most alternatives. I'd still be looking at median-of-medians, but that's a fair bit of extra work (so much so that it isn't really even quicksort anymore).
- jchonphoenix 16y ago
  ... Why does nobody understand how the adversarial method works? What I'm basically saying is that the usage of the comparator to create elements on the fly IS NOT LEGAL if you are trying to break randomized quicksort because this requires the adversary to have PRIOR KNOWLEDGE of the elements. He doesn't if its randomized.
  - sesqu 16y ago
    First of all, we're not trying to break a proof of anything. There's a demonstrated attack on comparator-based sorts. Whether you want to allow the scenario doesn't much change the fact that that scenario is vulnerable. Second, this method does not require prior knowledge of the elements. In fact, it disallows a large amount of information (the ordering). What prior knowledge are you claiming the adversary doesn't have but requires? He provides the set, so he has full knowledge of the members of the set (though the sorter doesn't, so this is useless knowledge). It's an unordered set with a full ordering relation, so a random permutation on initial indices will have no effect. He is the comparator, and thus has full knowledge of that as well. There is nothing else to know. Now, you might object to the fact that the comparator is not a deterministic automaton, which is the assumption exploited, and I wish you good luck in enforcing that in your sorting routines.
    - jchonphoenix 16y ago
      Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversary exactly and why this adversary does not kill randomized quick sort. Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
      - sesqu 16y ago
        I don't have that book, so you'll have to explain the reasoning if you want to convince me. I did find the MIT OCW lecture transcript on randomized quicksort, based on the book, and it described how randomization probably defeats an adversary supplying a worst-case initial permutation when the pivoting algorithm is known. That's a different adversary to the one we are discussing, even if relaxed; it has to supply an input that is consistent and fixed. They also motivated the scenario in terms of competition, which I find less reasonable than actual malevolence, but that bears little relevance now. When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.
gjm11 16y ago
McIlroy is not claiming to have done what you call "breaking randomized quicksort". Therefore the fact that he hasn't done that doesn't mean that he made a mistake or said anything untrue. That is all.

sesqu 16y ago

Stop thinking about arrays. Think ordered relations. Think collections and comparators. The sort is vulnerable to an attack at the highest abstraction level, where only necessary conditions are used. The usual implementation, using arrays of integers, is not similarly vulnerable. I'm not a fan of randomized algorithms, incidentally. It's selling your best case upriver to ward off offensive poisoning, and adds a multiplier to running time. Still, if you're offline, memory-restricted, timesharing and public-facing, I guess randomized quicksort's better than most alternatives. I'd still be looking at median-of-medians, but that's a fair bit of extra work (so much so that it isn't really even quicksort anymore).

jchonphoenix 16y ago
... Why does nobody understand how the adversarial method works? What I'm basically saying is that the usage of the comparator to create elements on the fly IS NOT LEGAL if you are trying to break randomized quicksort because this requires the adversary to have PRIOR KNOWLEDGE of the elements. He doesn't if its randomized.
- sesqu 16y ago
  First of all, we're not trying to break a proof of anything. There's a demonstrated attack on comparator-based sorts. Whether you want to allow the scenario doesn't much change the fact that that scenario is vulnerable. Second, this method does not require prior knowledge of the elements. In fact, it disallows a large amount of information (the ordering). What prior knowledge are you claiming the adversary doesn't have but requires? He provides the set, so he has full knowledge of the members of the set (though the sorter doesn't, so this is useless knowledge). It's an unordered set with a full ordering relation, so a random permutation on initial indices will have no effect. He is the comparator, and thus has full knowledge of that as well. There is nothing else to know. Now, you might object to the fact that the comparator is not a deterministic automaton, which is the assumption exploited, and I wish you good luck in enforcing that in your sorting routines.
  - jchonphoenix 16y ago
    Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversary exactly and why this adversary does not kill randomized quick sort. Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
    - sesqu 16y ago
      I don't have that book, so you'll have to explain the reasoning if you want to convince me. I did find the MIT OCW lecture transcript on randomized quicksort, based on the book, and it described how randomization probably defeats an adversary supplying a worst-case initial permutation when the pivoting algorithm is known. That's a different adversary to the one we are discussing, even if relaxed; it has to supply an input that is consistent and fixed. They also motivated the scenario in terms of competition, which I find less reasonable than actual malevolence, but that bears little relevance now. When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.

gjm11 16y ago

McIlroy is not claiming to have done what you call "breaking randomized quicksort". Therefore the fact that he hasn't done that doesn't mean that he made a mistake or said anything untrue. That is all.