Computing with noise: phase transitions in boolean formulas

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

Full description

Saved in:
Bibliographic Details
Published in:Physical review letters 2009-12, Vol.103 (24), p.248701-248701, Article 248701
Main Authors: Mozeika, Alexander, Saad, David, Raymond, Jack
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0031-9007
1079-7114
DOI:10.1103/PhysRevLett.103.248701