Scientific Calendar Event



Starts 6 Jul 2010 12:30
Ends 6 Jul 2010 20:00
Central European Time
ICTP
Leonardo da Vinci Building Luigi Stasi Seminar Room
Strada Costiera, 11 I - 34151 Trieste (Italy)
Noise is inherent in most forms of computing and its impact is more dramatic as the computing circuits become more complex and of large scale. Classical computing circuits suffer from thermal noise and production errors, quantum computers suffer from decoherence, whilst an understanding of noisy processes, inherent in neural networks and biological systems, remains poorly understood. The first model of noisy computation was proposed by von Neumann in 1956 who used circuits/formulas composed of noisy Boolean gates to gain insight into the robustness of biological neuronal networks. A noisy circuit cannot perform any given computation in a deterministic manner: for any circuit-input there is a non-vanishing probability that the circuit will produce the wrong output. Von Neumann showed that reliable computation (probability of error < 1/2) is possible for small gate-noise values and specific gates, and demonstrated how reliability can be improved using noisy gates only. In a more recent analysis Pippenger demonstrated that formulas only compute reliably up to a certain gate-noise threshold and that reliable computation with noisy gates requires strictly greater formula-depth. A number of papers have followed which improved and extended these results. The latter mainly rely on specific circuit constructions and methods that correspond to the worst case analysis. In this talk we show how random Boolean formulas can be mapped onto a physical framework and employ methods of statistical physics, developed specifically to analyze the typical behavior of random disordered systems, to gain insight into the behavior of noisy Boolean random formulas. We show that the typical-case macroscopic behavior observed corresponds straightforwardly to the bounds obtained in the theoretical computer science literature. Being very general, the framework is extended to consider further properties of random Boolean formulas for different gates and their dependence on the gate-noise level and formula depth.
  • M. Poropat