@Scott_Aaronson: Previously, you had said the problem is solved with certainty after O(1) queries (which you had to, to satisfy the objection). Now, you’re saying that after O(1) queries, it’s merely a “high probability”. Did you not change which claim you were defending?
Second, how can the required number of queries not depend on the problem size?
Finally, isn’t your example a special case of exactly the situation Eliezer_Yudkowsky describes in this post? In it, he pointed out that the “worst case” corresponds to an adversary who knows your algorithm. But if you specifically exclude that possibility, then a deterministic algorithm is just as good as the random one, because it would have the same correlation with a randomly chosen string. (It’s just like the case in the lockpicking problem: guessing all the sequences in order has no advantage over randomly picking and crossing off your list.) The apparent success of randomness is again due to, “acting so crazy that a superintelligent opponent can’t predict you”.
Which is why I summarize Eliezer_Yudkowsky’s position as: “Randomness is like poison. Yes, it can benefit you, but only if you use it on others.”
@Scott_Aaronson: Previously, you had said the problem is solved with certainty after O(1) queries (which you had to, to satisfy the objection). Now, you’re saying that after O(1) queries, it’s merely a “high probability”. Did you not change which claim you were defending?
Second, how can the required number of queries not depend on the problem size?
Finally, isn’t your example a special case of exactly the situation Eliezer_Yudkowsky describes in this post? In it, he pointed out that the “worst case” corresponds to an adversary who knows your algorithm. But if you specifically exclude that possibility, then a deterministic algorithm is just as good as the random one, because it would have the same correlation with a randomly chosen string. (It’s just like the case in the lockpicking problem: guessing all the sequences in order has no advantage over randomly picking and crossing off your list.) The apparent success of randomness is again due to, “acting so crazy that a superintelligent opponent can’t predict you”.
Which is why I summarize Eliezer_Yudkowsky’s position as: “Randomness is like poison. Yes, it can benefit you, but only if you use it on others.”