Computing with noise: phase transitions in Boolean formulas

Alexander Mozeika; David Saad; Jack Raymond

doi:10.1103/PhysRevLett.103.248701

Computing with noise: phase transitions in Boolean formulas

Alexander Mozeika, David Saad, Jack Raymond

College of Engineering and Physical Sciences

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

Abstract

Computing circuits composed of noisy logical gates and their ability to represent arbitrary Boolean functions with a given level of error are investigated within a statistical mechanics setting. Existing bounds on their performance are straightforwardly retrieved, generalized, and identified as the corresponding typical-case phase transitions. Results on error rates, function depth, and sensitivity, and their dependence on the gate-type and noise model used are also obtained.

Original language	English
Article number	248701
Pages (from-to)	248701
Number of pages	1
Journal	Physical Review Letters
Volume	103
Issue number	24
DOIs	https://doi.org/10.1103/PhysRevLett.103.248701
Publication status	Published - 11 Dec 2009

Bibliographical note

Keywords

Computing circuits
noisy logical gates
Boolean functions
given level of error
statistical mechanics

Access to Document

10.1103/PhysRevLett.103.248701

NoisyComputationPRL_v3.pdf
© 2009 The American Physical Society

http://link.aps.org/doi/10.1103/PhysRevLett.103.248701

Cite this

@article{d1d02f847c794f02a8f649ed8e349bfc,

title = "Computing with noise: phase transitions in Boolean formulas",

abstract = "Computing circuits composed of noisy logical gates and their ability to represent arbitrary Boolean functions with a given level of error are investigated within a statistical mechanics setting. Existing bounds on their performance are straightforwardly retrieved, generalized, and identified as the corresponding typical-case phase transitions. Results on error rates, function depth, and sensitivity, and their dependence on the gate-type and noise model used are also obtained.",

keywords = "Computing circuits, noisy logical gates, Boolean functions, given level of error, statistical mechanics",

author = "Alexander Mozeika and David Saad and Jack Raymond",

note = "{\textcopyright} 2009 The American Physical Society",

year = "2009",

month = dec,

day = "11",

doi = "10.1103/PhysRevLett.103.248701",

language = "English",

volume = "103",

pages = "248701",

journal = "Physical Review Letters",

issn = "0031-9007",

publisher = "American Physical Society",

number = "24",

}

TY - JOUR

T1 - Computing with noise: phase transitions in Boolean formulas

AU - Mozeika, Alexander

AU - Saad, David

AU - Raymond, Jack

PY - 2009/12/11

Y1 - 2009/12/11

N2 - Computing circuits composed of noisy logical gates and their ability to represent arbitrary Boolean functions with a given level of error are investigated within a statistical mechanics setting. Existing bounds on their performance are straightforwardly retrieved, generalized, and identified as the corresponding typical-case phase transitions. Results on error rates, function depth, and sensitivity, and their dependence on the gate-type and noise model used are also obtained.

AB - Computing circuits composed of noisy logical gates and their ability to represent arbitrary Boolean functions with a given level of error are investigated within a statistical mechanics setting. Existing bounds on their performance are straightforwardly retrieved, generalized, and identified as the corresponding typical-case phase transitions. Results on error rates, function depth, and sensitivity, and their dependence on the gate-type and noise model used are also obtained.

KW - Computing circuits

KW - noisy logical gates

KW - Boolean functions

KW - given level of error

KW - statistical mechanics

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

U2 - 10.1103/PhysRevLett.103.248701

DO - 10.1103/PhysRevLett.103.248701

M3 - Article

SN - 0031-9007

VL - 103

SP - 248701

JO - Physical Review Letters

JF - Physical Review Letters

IS - 24

M1 - 248701

ER -

Computing with noise: phase transitions in Boolean formulas

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this