Timeline for Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 15, 2020 at 22:15 | comment | added | gnasher729 | Feel free to post a better answer. I'm looking forward to it. If none is forthcoming then I will draw my conclusions. | |
| Jan 14, 2020 at 23:37 | comment | added | Aaron Rotenberg | This does not answer the question. Whether a probabilistic multiplication circuit using $O(n \log n)$ gates has any practical use is irrelevant to the question, which is whether such a circuit exists. Also, a bounded-error probabilistic algorithm by definition will not get any product consistently wrong, but only wrong with a bounded probability over the random bits. | |
| Aug 17, 2019 at 20:06 | history | answered | gnasher729 | CC BY-SA 4.0 |