On reliable computation by noisy random Boolean formulas

Alexander Mozeika, David Saad

Research output: Contribution to journalArticlepeer-review


We study noisy computation in randomly generated k-ary Boolean formulas. We establish bounds on the noise level above which the results of computation by random formulas are not reliable. This bound is saturated by formulas constructed from a single majority-like gate. We show that these gates can be used to compute any Boolean function reliably below the noise bound.

Original languageEnglish
Pages (from-to)637-644
Number of pages8
JournalIEEE Transactions on Information Theory
Issue number1
Early online date13 Nov 2014
Publication statusPublished - Jan 2015

Bibliographical note

© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.


  • random Boolean formulas
  • reliable computation
  • Çε-noise


Dive into the research topics of 'On reliable computation by noisy random Boolean formulas'. Together they form a unique fingerprint.

Cite this