Interesting post. I suppose one could argue that the Born rule in quantum physics has a special status when making a list like this. Also why is shot noise weirder than Poisson noise? Aren't they synonymous? Is cryptographic hashing considered a randomized algorithm? It is fully deterministic but generates something that largely behaves as if uniformly random (which itself is its highly useful deliverable).
Re: Shot noise, I just meant that the physics behind it is weird, but definitely stochastic. Shot noise is well modeled by Poisson, but so are other physical processes.
Re: crypto, I don't have an opinion! For the purposes of the algorithms I have in mind, I want to be as pragmatic as possible: as long as the randomness repeatably looks random enough, that's good enough for practice.
But I definitely know that some stats packages used PRNGs that had very short recurrence times. Don't do this! (Example: https://arxiv.org/abs/1810.10985)
Great question. I think I'm going to do a whole week on "intervals" in statistics. There's so much to say, and they are so confusing. I will definitely devote a bunch of that conversation to conformal.
We think (subject to caveats of "this isn't, and maybe won't ever be, practical") that efficient randomized algorithms can be provably* transformed into efficient deterministic ones. In that case, you'd have a use for randomness (in constructing and analyzing them) despite the fact that we don't need random bits for anything!
*in 100 years when we can finally prove circuit lower bounds
Interesting post. I suppose one could argue that the Born rule in quantum physics has a special status when making a list like this. Also why is shot noise weirder than Poisson noise? Aren't they synonymous? Is cryptographic hashing considered a randomized algorithm? It is fully deterministic but generates something that largely behaves as if uniformly random (which itself is its highly useful deliverable).
Re: Shot noise, I just meant that the physics behind it is weird, but definitely stochastic. Shot noise is well modeled by Poisson, but so are other physical processes.
Re: crypto, I don't have an opinion! For the purposes of the algorithms I have in mind, I want to be as pragmatic as possible: as long as the randomness repeatably looks random enough, that's good enough for practice.
But I definitely know that some stats packages used PRNGs that had very short recurrence times. Don't do this! (Example: https://arxiv.org/abs/1810.10985)
only tangentially related but can you tell us if conformal prediction is the be all end all for UQ? feels like everything these days is conformal
Great question. I think I'm going to do a whole week on "intervals" in statistics. There's so much to say, and they are so confusing. I will definitely devote a bunch of that conversation to conformal.
We think (subject to caveats of "this isn't, and maybe won't ever be, practical") that efficient randomized algorithms can be provably* transformed into efficient deterministic ones. In that case, you'd have a use for randomness (in constructing and analyzing them) despite the fact that we don't need random bits for anything!
*in 100 years when we can finally prove circuit lower bounds
Hah. Love it.
More seriously: are there any glimmers of hope in derandomization? Have people made any tangible progress?