Timeline for Pseudorandom generators
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 12, 2016 at 1:19 | comment | added | Andrew | I'm assuming that's not known but would be interested in confirmation. | |
| Oct 11, 2016 at 18:14 | comment | added | Andrew | To be clear, if general purpose pseudorandom generators exist, then we have $\mathbf{P}=\mathbf{BPP}$? | |
| Oct 21, 2010 at 3:39 | comment | added | didest | One detail: there is a particular poly-time computable function that is one-way iff they exist. See cs.cornell.edu/courses/cs687/2006fa/lectures/lecture5.pdf | |
| Nov 1, 2009 at 9:30 | comment | added | Harrison Brown | Right, that's open, and I think the current situation is that we're as clueless about how to approach it as we are to approaching P vs. NP itself. There are also some crypto questions relating to trapdoor OWFs useful in public-key systems, but I don't understand those very well (my interests are more toward derandomization.) | |
| Nov 1, 2009 at 9:16 | comment | added | Ilya Nikokoshev |
So, there is a still one more open question: even assuming P != NP, it is not know whether one-way functions (= PRNG) exist?
|
|
| Nov 1, 2009 at 9:15 | comment | added | Harrison Brown | No problem -- this way someone can add the reference I can't find, anyway. | |
| Nov 1, 2009 at 9:10 | vote | accept | Ilya Nikokoshev | ||
| Nov 1, 2009 at 9:01 | history | edited | Harrison Brown | CC BY-SA 2.5 |
added 152 characters in body
|
| Nov 1, 2009 at 8:55 | history | answered | Harrison Brown | CC BY-SA 2.5 |