Noisy random Boolean formulae: a statistical physics perspective

Alexander Mozeika, David Saad, Jack Raymond

Research output: Contribution to journalArticlepeer-review

Abstract

Properties of computing Boolean circuits composed of noisy logical gates are studied using the statistical physics methodology. A formula-growth model that gives rise to random Boolean functions is mapped onto a spin system, which facilitates the study of their typical behavior in the presence of noise. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding macroscopic phase transitions. The framework is employed for deriving results on error-rates at various function-depths and function sensitivity, and their dependence on the gate-type and noise model used. These are difficult to obtain via the traditional methods used in this field.
Original languageEnglish
Article number041112
JournalPhysical Review E
Volume82
Issue number041112
DOIs
Publication statusPublished - 14 Oct 2010

Bibliographical note

© American Physical Society

Keywords

  • computing Boolean circuits
  • noisy logical gates

Fingerprint

Dive into the research topics of 'Noisy random Boolean formulae: a statistical physics perspective'. Together they form a unique fingerprint.

Cite this