On the robustness of random Boolean formulae

Mozeika, Alexander, Saad, David and Raymond, Jack (2010). On the robustness of random Boolean formulae. Journal of Physics, 233 (1),

Abstract

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: Engineering & Applied Sciences > Systems analytics research institute (SARI)
Engineering & Applied Sciences > Mathematics
Engineering & Applied 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
Full Text Link: http://iopscien ... 6/233/1/012015/
Related URLs: http://www.scop ... tnerID=8YFLogxK (Scopus URL)
Published Date: 2010-07-19
Authors: Mozeika, Alexander
Saad, David ( 0000-0001-9821-2623)
Raymond, Jack

Download

[img]

Version: Draft Version


Export / Share Citation


Statistics

Additional statistics for this record