On reliable computation by noisy random Boolean formulas

Alexander Mozeika, David Saad

Research output: Contribution to journalArticle

Abstract

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
Volume61
Issue number1
Early online date13 Nov 2014
DOIs
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.

Keywords

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

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

  • Cite this