How is using randomness in stochastic computing connected to how algorithms (eg in the complexity class BPP) use randomness to solve problems?
replies(1):
[please forgive my grammar]
1. There is noisy computers which can work despite or because some unreliable part. Neural netwroks are quite ok with it for example, so some people speculate that it will be possible to build specialized noisy circuits for specific networks. 2. There is stochastic computing, in which complicated numerical functions represented as probability density distributions (?) 3. And then there is probabalistic computing, when state randomly updated in accordance with some "temprature". 4. And finally there is randomized algoritms, which are closer to classical computer science but with some stream of input. Howver, people like Avi Wigderson who succesfully removed the "random" parts of those algoritms.
Plus there is funny things with non-associativity of floating-point numbers which can lead to non-determinism when the order of execution (summation for example) is arbitary, which can lead to funny results. But because neural netwroks are robust to noise to some degree, it will still work.
And the stuff which done by Avi Wigderson requires that computers work in determinstic way (except of that random stream), so it will not be very compatible with unreliable noisy computations. However, it seems that stochastic, probabalistic and noisy computations could be combined.