Silas is right; Scott keeps changing the definition in the middle, which was exactly my original complaint.
For example, Scott says: In the randomized case, just keep picking random bits and querying them. After O(1) queries, with high probability you’ll have queried either a 1 in the left half or a 1 in the right half, at which point you’re done.
And yet this is no different from a deterministic algorithm. It can also query O(1) bits, and “with high probability” have a certain answer.
I’m really astonished that Scott can’t see the slight-of-hand in his own statement. Here’s how he expresses the challenge: It’s clear that any deterministic algorithm needs to examine at least n/4 + 1 of the bits to solve this problem. On the other hand, a randomized sampling algorithm can solve the problem with certainty after looking at only O(1) bits on average.
Notice that tricky final phrase, on average? That’s vastly weaker than what he is forcing the deterministic algorithm to do. The “proof” that a deterministic algorithm requires n/4+1 queries requires a goal much more difficult than getting a quick answer “on average”.
If you’re willing to consider a goal of answering quickly only “on average”, then a deterministic algorithm can also do it just as fast (on average) as your randomized algorithm.
Silas is right; Scott keeps changing the definition in the middle, which was exactly my original complaint.
For example, Scott says: In the randomized case, just keep picking random bits and querying them. After O(1) queries, with high probability you’ll have queried either a 1 in the left half or a 1 in the right half, at which point you’re done.
And yet this is no different from a deterministic algorithm. It can also query O(1) bits, and “with high probability” have a certain answer.
I’m really astonished that Scott can’t see the slight-of-hand in his own statement. Here’s how he expresses the challenge: It’s clear that any deterministic algorithm needs to examine at least n/4 + 1 of the bits to solve this problem. On the other hand, a randomized sampling algorithm can solve the problem with certainty after looking at only O(1) bits on average.
Notice that tricky final phrase, on average? That’s vastly weaker than what he is forcing the deterministic algorithm to do. The “proof” that a deterministic algorithm requires n/4+1 queries requires a goal much more difficult than getting a quick answer “on average”.
If you’re willing to consider a goal of answering quickly only “on average”, then a deterministic algorithm can also do it just as fast (on average) as your randomized algorithm.