On reliable computation by noisy random Boolean formulas

Alexander Mozeika; David Saad

doi:10.1109/TIT.2014.2370638

On reliable computation by noisy random Boolean formulas

Alexander Mozeika, David Saad

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	637-644
Number of pages	8
Journal	IEEE Transactions on Information Theory
Volume	61
Issue number	1
Early online date	13 Nov 2014
DOIs	https://doi.org/10.1109/TIT.2014.2370638
Publication status	Published - 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

Access to Document

10.1109/TIT.2014.2370638

Reliable computation by noisy random Boolean formulas
© 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.
Accepted author manuscript, 122 KB

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, {\c C}ε-noise",

author = "Alexander Mozeika and David Saad",

note = "{\textcopyright} 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 = jan,

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",

}

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

UR - http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6955823

U2 - 10.1109/TIT.2014.2370638

DO - 10.1109/TIT.2014.2370638

M3 - Article

AN - SCOPUS:84920181616

SN - 0018-9448

VL - 61

SP - 637

EP - 644

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 1

ER -

On reliable computation by noisy random Boolean formulas

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this