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.

Publication DOI:
Divisions: College of Engineering & Physical Sciences > School of Informatics and Digital Engineering > Mathematics
College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
College of Engineering & Physical Sciences
Additional Information: © 2009 The American Physical Society
Uncontrolled Keywords: Computing circuits,noisy logical gates,Boolean functions,given level of error,statistical mechanics,Physics and Astronomy(all)
Publication ISSN: 1079-7114
Full Text Link: http://link.aps ... Lett.103.248701
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2009-12-11
Authors: Mozeika, Alexander
Saad, David (ORCID Profile 0000-0001-9821-2623)
Raymond, Jack

Export / Share Citation


Additional statistics for this record