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