the claim was that when you can improve an algorithm by randomizing it, you can improve it further by derandomizing it
Unknowns:
randomness wasn’t necessary in order to achieve the best result, not that it is always possible to achieve a result better than what randomness achieves
I think a claim that a randomized algorithm is never better than some deterministic one is interesting and probably true (possibly not, which is why it’s interesting). Is Eliezer really making an even stronger claim than this? Is any precise claim being made? The meaning of “improving an algorithm by adding (or removing) randomization” is pretty vague. Improving in what way? Isn’t any non-randomized algorithm technically a member of “randomized algorithms”? If not, can’t it be made technically randomized at no asymptotic cost?
Eliezer:
Unknowns:
I think a claim that a randomized algorithm is never better than some deterministic one is interesting and probably true (possibly not, which is why it’s interesting). Is Eliezer really making an even stronger claim than this? Is any precise claim being made? The meaning of “improving an algorithm by adding (or removing) randomization” is pretty vague. Improving in what way? Isn’t any non-randomized algorithm technically a member of “randomized algorithms”? If not, can’t it be made technically randomized at no asymptotic cost?