Noisy random Boolean formulae:a statistical physics perspective


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.

Publication DOI:
Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
College of Engineering & Physical Sciences
Additional Information: © American Physical Society
Uncontrolled Keywords: computing Boolean circuits,noisy logical gates,Condensed Matter Physics,Statistical and Nonlinear Physics,Statistics and Probability
Publication ISSN: 1550-2376
Last Modified: 03 Jan 2024 08:04
Date Deposited: 20 Apr 2012 09:23
Full Text Link: http://link.aps ... sRevE.82.041112
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2010-10-14
Authors: Mozeika, Alexander
Saad, David (ORCID Profile 0000-0001-9821-2623)
Raymond, Jack



Version: Published Version

Export / Share Citation


Additional statistics for this record