Posts
Comments
DonGeddis is missing the point. Randomness does buy power. The simplest example is sampling in statistics: to estimate the fraction of read-headed people in the world to within 5% precision and with confidence 99%, it is enough to draw a certain number of random samples and compute the fraction of read-headed people in the sample. The number of samples required is independent of the population size. No deterministic algorithm can do this, not even if you try to simulate samples by using good PRNGs, because there are ``orderings'' of the world's population that would fool your algorithm. But if you use random bits that are independent of the data, you cannot be fooled. (By the way, whether 'true randomness' is really possible in the real world is a totally different issue.)
Note that, for decision problems, randomness is not believed to give you a more-than-polynomial speedup (this is the P vs BPP question). But neither sampling nor the promise problem Scott mentioned are decision problems (defined on all inputs).
Regarding your claim that you cannot compare 'worst-case time' for deterministic algorithms with 'worst-case expected time' for randomized ones: this is totally pointless and shows a total lack of understanding of randomization. No one claims that you can have a randomized algorithm with success probability one that outperforms the deterministic algorithm. So either we use the expected running time or the randomized algorithm, or we allow a small error probability.
We can choose either one and use the same definition of the problem for both deterministic and randomized. Take Scott example and suppose we want algorithms that succeed with probability 2/3 at least, on every input. The goal is the same in both cases, so they are comparable. In the case of deterministic algorithms, this implies always getting the correct answer. DonGeddis seems not to realize this, and contrary to what he says, any deterministic algorithm, no matter how clever, needs to look at n/4+1 elements in the worst case. (By the way, maybe DonGeddis problem is that he doesn't see the proof of this fact, but it easily provable with standard techniques.) However, a randomized algorithm that makes a worst-case constant number of queries will succeed with probability 2/3. If we want higher succeed probability, we can just repeat a constant number of times. Note that I'm not talking about the expected complexity but about worst-case complexity, if the former bothers you; this comes at the expense of a small error probability.
As for Blum's paper, it shows that the best bounds we can prove for randomized algorithms in that particular problem outperform the bounds we can prove for deterministic algorithms. Sure, that does not imply the former are better, but it's the best bound we can prove. To prove that the randomized algorithm in this case has a better constant, one needs to find a lower bound for the deterministic algorithm.
DonGeddis is missing the point. Randomness does buy power. The simplest example is sampling in statistics: to estimate the fraction of read-headed people in the world to within 5% precision and with confidence 99%, it is enough to draw a certain number of random samples and compute the fraction of read-headed people in the sample. The number of samples required is independent of the population size. No deterministic algorithm can do this, not even if you try to simulate samples by using good PRNGs, because there are ``orderings'' of the world's population that would fool your algorithm. But if you use random bits that are independent of the data, you cannot be fooled. (By the way, whether 'true randomness' is really possible in the real world is a totally different issue.)
Note that, for decision problems, randomness is not believed to give you a more-than-polynomial speedup (this is the P vs BPP question). But neither sampling nor the promise problem Scott mentioned are decision problems (defined on all inputs).
Regarding your claim that you cannot compare 'worst-case time' for deterministic algorithms with 'worst-case expected time' for randomized ones: this is totally pointless and shows a total lack of understanding of randomization. No one claims that you can have a randomized algorithm with success probability one that outperforms the deterministic algorithm. So either we use the expected running time or the randomized algorithm, or we allow a small error probability.
We can choose either one and use the same definition of the problem for both deterministic and randomized. Take Scott example and suppose we want algorithms that succeed with probability 2/3 at least, on every input. The goal is the same in both cases, so they are comparable. In the case of deterministic algorithms, this implies always getting the correct answer. DonGeddis seems not to realize this, and contrary to what he says, any deterministic algorithm, no matter how clever, needs to look at n/4+1 elements in the worst case. (By the way, maybe DonGeddis problem is that he doesn't see the proof of this fact, but it easily provable with standard techniques.) However, a randomized algorithm that makes a worst-case constant number of queries will succeed with probability 2/3. If we want higher succeed probability, we can just repeat a constant number of times. Note that I'm not talking about the expected complexity but about worst-case complexity, if the former bothers you; this comes at the expense of a small error probability.
As for Blum's paper, it shows that the best bounds we can prove for randomized algorithms in that particular problem outperform the bounds we can prove for deterministic algorithms. Sure, that does not imply the former are better, but it's the best bound we can prove. To prove that the randomized algorithm in this case has a better constant, one needs to find a lower bound for the deterministic algorithm.