Timeline for Efficient sampling of primes
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2020 at 7:12 | comment | added | user21820 | @EmilJeřábek: What if you allow the random source to return a uniformly random number in the range ${1..n}$ for any input natural $n$? Then you can produce any rational probability distribution with finite support in $O(1)$ time. | |
| Oct 15, 2020 at 16:06 | comment | added | Mahdi Cheraghchi | Fair enough. One has to look for an idealized model where such issues can be circumvented. | |
| Oct 15, 2020 at 7:27 | comment | added | Emil Jeřábek | Not to mention that no randomized algorithm with any worst-case bound whatsoever on the running time can produce exactly even the uniform distribution on $3$ elements. The distribution produced by any such algorithm has all probabilities integer multiples of $2^{-t(n)}$, where $t(n)$ is the bound on running time. | |
| Oct 15, 2020 at 6:05 | comment | added | Emil Jeřábek | Worst-case polynomial? No such thing is known even remotely. There is no known polynomial-time algorithm that given $N$, computes a prime between $N$ and $2N$. | |
| Oct 14, 2020 at 22:49 | history | asked | Mahdi Cheraghchi | CC BY-SA 4.0 |