Computing with Noise: Phase Transitions in Boolean Formulas
Alexander Mozeika, David Saad, Jack Raymond · Physical Review Letters · 2009
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. Existing bounds on their performance are straightforwardly retrieved, generalized, and identified as the corresponding typical-case phase transitions. Results on error rates, function depth, and sensitivity, and their dependence on the gate-type and noise model used are also obtained.