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