Computing with noise: phase transitions in Boolean formulas

Alexander Mozeika, David Saad, Jack Raymond

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Article number248701
Pages (from-to)248701
Number of pages1
JournalPhysical Review Letters
Issue number24
Publication statusPublished - 11 Dec 2009

Bibliographical note

© 2009 The American Physical Society


  • Computing circuits
  • noisy logical gates
  • Boolean functions
  • given level of error
  • statistical mechanics


Dive into the research topics of 'Computing with noise: phase transitions in Boolean formulas'. Together they form a unique fingerprint.

Cite this