2 ms·
I wonder if there's an underlying "random attempts" theory that can tie these successes (that have intrigued me for a long time): 1. Shannon's random code book
by beagle3 14y ago
I wonder if there's an underlying "random attempts" theory that can tie these successes (that have intrigued me for a long time):
1. Shannon's random code book construction (for achieving the noisy channel rate limit)
2. Johnson-Lindenstrauss lemma http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_l..., the result that underlies most if not all of the compressive sensing field (and all of the recent superfast large scale SVD, PCA algorithms)
And of course this recent result might also be related somehow.
- eru 14y agoThere's also the (bigger?) question whether randomness helps at all, e.g. whether P is weaker than P + a source of random bits. In practice, randomization does help, but like with P vs NP as far as I know nobody has proven anything definite.
- pmb 14y agoThe complexity classes that involve randomness have names like BPP, ZPP, and RP. BPP is usually the one people mean when they talk about practical problems that randomness might help solve. Although the second level of PH contains both NP and BPP, which both contain P, it is still not known if any of those containments are proper, and the relationship between BPP and NP is still open. Even more interesting is the relationship between BPP and its quantum version BQP. The Complexity Zoo has more for the interested reader... http://qwiki.stanford.edu/index.php/Complexity_Zoo http://qwiki.stanford.edu/index.php/Complexity_Zoo
- eru 14y agoThanks for giving a less hand-wavy account.