On the robustness of random Boolean formulae

Alexander Mozeika, David Saad, Jack Raymond

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
JournalJournal of Physics: Conference Series
Issue number1
Publication statusPublished - 19 Jul 2010
EventInternational Workshop on Statistical-Mechanical Informatics 2010 - Kyoto, Japan
Duration: 7 Mar 201010 Mar 2010

Bibliographical note

Published under licence in the Journal of Physics: Conference Series by IOP Publishing Ltd.


  • random Boolean formulae
  • noisy logical gates


Dive into the research topics of 'On the robustness of random Boolean formulae'. Together they form a unique fingerprint.

Cite this