Computing with noise: phase transitions in boolean formulas.
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.
Mozeika
Alexander
A
The Nonlinearity and Complexity Research Group, Aston University, Birmingham B4 7ET, United Kingdom.
Saad
David
D
Raymond
Jack
J