Computing with Noise - Phase Transitions in Boolean Formulas
arXiv:0908.3981 · doi:10.1103/PhysRevLett.103.248701
Abstract
Computing circuits composed of noisy logical gates and their ability to represent arbitrary Boolean functions with a given level of error are investigated within a statistical mechanics setting. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding typical-case phase transitions. This framework paves the way for obtaining new results on error-rates, function-depth and sensitivity, and their dependence on the gate-type and noise model used.
10 pages, 2 figures
Cited by in corpus (7)
- Noisy Random Boolean Formulae - a Statistical Physics Perspective
- Exploring the Function Space of Deep-Learning Machines
- Large Deviation Analysis of Function Sensitivity in Random Deep Neural Networks
- Space of Functions Computed by Deep-Layered Machines
- Characterizing short-term stability for Boolean networks over any distribution of transfer functions
- The behavior of noise-resilient Boolean networks with diverse topologies
- Phase transitions and memory effects in the dynamics of Boolean networks