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.
|Journal||Journal of Physics: Conference Series|
|Publication status||Published - 19 Jul 2010|
|Event||International Workshop on Statistical-Mechanical Informatics 2010 - Kyoto, Japan|
Duration: 7 Mar 2010 → 10 Mar 2010
Bibliographical notePublished under licence in the Journal of Physics: Conference Series by IOP Publishing Ltd.
- random Boolean formulae
- noisy logical gates