Timeline for Probability Distributions and Computational Complexity
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2016 at 10:11 | answer | added | Kaveh | timeline score: 2 | |
| Jun 17, 2014 at 8:40 | comment | added | Martin Berger | @vzn Yes, I know that paper. It's another illustration of the difficulty my question is referring to. | |
| Jun 17, 2014 at 1:31 | comment | added | vzn | your question reminded me of this paper. seems related. what do you think? The halting problem is decidable on a set of asymptotic probability one Hamkins/Miasnikov | |
| Jun 12, 2014 at 17:18 | comment | added | Martin Berger | @NikosM. Thanks, but that link too doesn't say anything about the complexity of the underlying distribution. The reference talks about a transformation $\phi$ on the uniform distribution. But that transformation might be hard / or easy computationally. | |
| Jun 12, 2014 at 17:11 | comment | added | Nikos M. | @MartinBerger, the stats.se link actually uses the theorem, the theorem is sth like the one stated here and here, this is basic probability results nothing more than that | |
| Jun 12, 2014 at 10:06 | comment | added | Martin Berger | @NikosM. I'm not sure what that theorem is. The link you give doesn't appear to mention it. | |
| Jun 12, 2014 at 8:11 | comment | added | Nikos M. | Is the probability simulation theorem of any help? | |
| Jun 9, 2014 at 10:37 | comment | added | Martin Berger | @NicholasMancuso The examples I give are uniform distributions. But one can ask the same question about non-uniform distributions. One can also wonder about distributions on $\mathbb{R}$. As regards discrete distributions: prima facie, counting doesn't appear to be enough in general, you also need to be able to generate the $i$-th element, after you've uniformly chosen $i$. That said, it might be the case that counting is the core of the problem. | |
| Jun 9, 2014 at 0:58 | comment | added | vzn | seems broad... there are many probabilistic complexity classes & then also the PCP thm is quite significant. eg have you heard of BPP? there are also strong connections to quantum computing... there is a strong argument to be made that probability theory breaks down on undecidable problems because its all about stats/computable math. also average case complexity? PAC learning? | |
| Jun 8, 2014 at 21:49 | comment | added | Martin Berger | @NicholasMancuso I agree that counting + unform choice can always be used. So in some sense it gives an upper bound. Is this all that can be said? Where in the literature has this been investigated? | |
| Jun 8, 2014 at 18:16 | comment | added | Nicholas Mancuso | Both of your examples are discrete uniform distributions. I would imagine the differing complexities would be in how hard it is to count $|\chi|$ where $\chi$ is the support. | |
| Jun 8, 2014 at 9:18 | history | edited | Martin Berger | CC BY-SA 3.0 |
Clarified the question.
|
| Jun 7, 2014 at 17:19 | comment | added | Wandering Logic | Another interesting example (but which is decidable) is the quantum fourier transform. Given $f(k)=a^k \mod b$ return a number $l \in [0,N]$ such that the probability of $l$ is proportional to $\left|F(l)\right|$, $F(l) = \sum_{k=0}^N f(k) e^{-2\pi ikl/N}$. | |
| Jun 7, 2014 at 12:57 | history | tweeted | twitter.com/#!/StackCompSci/status/475260188203548672 | ||
| Jun 7, 2014 at 11:20 | history | edited | Martin Berger | CC BY-SA 3.0 |
edited body
|
| Jun 7, 2014 at 10:50 | history | asked | Martin Berger | CC BY-SA 3.0 |