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

Fingerprint

Boolean functions

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

Cite this

@article{a835bd03cc654cbcb629541bf7b6873d,
title = "On reliable computation by noisy random Boolean formulas",
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.",
keywords = "random Boolean formulas, reliable computation, {\cC}ε-noise",
author = "Alexander Mozeika and David Saad",
note = "{\circledC} 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.",
year = "2015",
month = "1",
doi = "10.1109/TIT.2014.2370638",
language = "English",
volume = "61",
pages = "637--644",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE",
number = "1",

}

On reliable computation by noisy random Boolean formulas. / Mozeika, Alexander; Saad, David.

In: IEEE Transactions on Information Theory, Vol. 61, No. 1, 01.2015, p. 637-644.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On reliable computation by noisy random Boolean formulas

AU - Mozeika, Alexander

AU - Saad, David

N1 - © 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.

PY - 2015/1

Y1 - 2015/1

N2 - 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.

AB - 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.

KW - random Boolean formulas

KW - reliable computation

KW - Çε-noise

UR - http://www.scopus.com/inward/record.url?scp=84920181616&partnerID=8YFLogxK

U2 - 10.1109/TIT.2014.2370638

DO - 10.1109/TIT.2014.2370638

M3 - Article

AN - SCOPUS:84920181616

VL - 61

SP - 637

EP - 644

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 1

ER -