On the robustness of random Boolean formulae


Random Boolean formulae, generated by a growth process of noisy logical gates are analyzed using the generating functional methodology of statistical physics. We study the type of functions generated for different input distributions, their robustness for a given level of gate error and its dependence on the formulae depth and complexity and the gates used. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding typical-case phase transitions. Results for error-rates, function-depth and sensitivity of the generated functions are obtained for various gate-type and noise models.

Publication DOI: https://doi.org/10.1088/1742-6596/233/1/012015
Divisions: College of Engineering & Physical Sciences > Systems analytics research institute (SARI)
College of Engineering & Physical Sciences
Additional Information: Published under licence in the Journal of Physics: Conference Series by IOP Publishing Ltd.
Uncontrolled Keywords: random Boolean formulae,noisy logical gates
Publication ISSN: 1742-6596
Last Modified: 03 Jan 2024 08:04
Date Deposited: 23 Apr 2012 12:20
Full Text Link: http://iopscien ... 6/233/1/012015/
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
PURE Output Type: Article
Published Date: 2010-07-19
Authors: Mozeika, Alexander
Saad, David (ORCID Profile 0000-0001-9821-2623)
Raymond, Jack



Version: Draft Version

Export / Share Citation


Additional statistics for this record