ID: 0908.3981

Computing with Noise - Phase Transitions in Boolean Formulas

August 27, 2009

View on ArXiv
Alexander Mozeika, David Saad, Jack Raymond
Condensed Matter
Computer Science
Disordered Systems and Neura...
Computational Complexity

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. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding typical-case phase transitions. This framework paves the way for obtaining new results on error-rates, function-depth and sensitivity, and their dependence on the gate-type and noise model used.

Similar papers 1

Noisy Random Boolean Formulae - a Statistical Physics Perspective

March 19, 2010

96% Match
Alexander Mozeika, David Saad, Jack Raymond
Disordered Systems and Neura...
Statistical Mechanics
Adaptation and Self-Organizi...

Typical properties of computing circuits composed of noisy logical gates are studied using the statistical physics methodology. A growth model that gives rise to typical random Boolean functions is mapped onto a layered Ising spin system, which facilitates the study of their ability to represent arbitrary formulae with a given level of error, the tolerable level of gate-noise, and its dependence on the formulae depth and complexity, the gates used and properties of the functi...

Find SimilarView on arXiv

On reliable computation by noisy random Boolean formulas

June 21, 2012

88% Match
Alexander Mozeika, David Saad
Disordered Systems and Neura...
Probability

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 gates. We show that these gates can be used to compute any Boolean function reliably below the noise bound.

Find SimilarView on arXiv

Bayesian Gates for Reliable Logical Operations under Noisy Condition

March 1, 2017

88% Match
Tetsuya J. Kobayashi
Other Computer Science

The reliability of logical operations is indispensable for the reliable operation of computational systems. Since the down-sizing of micro-fabrication generates non-negligible noise in these systems, a new approach for designing noise-immune gates is required. In this paper, we demonstrate that noise-immune gates can be designed by combining Bayesian inference theory with the idea of computation over a noisy signal. To reveal their practical advantages, the performance of the...

Find SimilarView on arXiv

Noise Limited Computational Speed

February 11, 2007

87% Match
Luca Gammaitoni
Hardware Architecture
Performance

In modern transistor based logic gates, the impact of noise on computation has become increasingly relevant since the voltage scaling strategy, aimed at decreasing the dissipated power, has increased the probability of error due to the reduced switching threshold voltages. In this paper we discuss the role of noise in a two state model that mimic the dynamics of standard logic gates and show that the presence of the noise sets a fundamental limit to the computing speed. An op...

Find SimilarView on arXiv

Noise based logic: why noise? A comparative study of the necessity of randomness out of orthogonality

April 11, 2012

86% Match
He Wen, Laszlo B. Kish
Other Computer Science
Emerging Technologies

Although noise-based logic shows potential advantages of reduced power dissipation and the ability of large parallel operations with low hardware and time complexity the question still persist: is randomness really needed out of orthogonality? In this Letter, after some general thermodynamical considerations, we show relevant examples where we compare the computational complexity of logic systems based on orthogonal noise and sinusoidal signals, respectively. The conclusion i...

Find SimilarView on arXiv
Alexander Mozeika, Bo Li, David Saad
Machine Learning
Disordered Systems and Neura...
Machine Learning

We study the space of functions computed by random-layered machines, including deep neural networks and Boolean circuits. Investigating the distribution of Boolean functions computed on the recurrent and layer-dependent architectures, we find that it is the same in both models. Depending on the initial conditions and computing elements used, we characterize the space of functions computed at the large depth limit and show that the macroscopic entropy of Boolean functions is e...

Noise-based information processing: Noise-based logic and computing: what do we have so far?

February 10, 2011

86% Match
Laszlo B. Kish, Sunil Khatri, Sergey Bezrukov, Ferdinand Peper, ... , Horvath Tamas
Emerging Technologies

We briefly introduce noise-based logic. After describing the main motivations we outline classical, instantaneous (squeezed and non-squeezed), continuum, spike and random-telegraph-signal based schemes with applications such as circuits that emulate the brain functioning and string verification via a slow communication channel.

Find SimilarView on arXiv

Thermodynamics of computing with circuits

June 11, 2018

86% Match
David Hilton Wolpert, Artemy Kolchinsky
Statistical Mechanics
Computational Complexity
Computational Physics

Digital computers implement computations using circuits, as do many naturally occurring systems (e.g., gene regulatory networks). The topology of any such circuit restricts which variables may be physically coupled during the operation of a circuit. We investigate how such restrictions on the physical coupling affects the thermodynamic costs of running the circuit. To do this we first calculate the minimal additional entropy production that arises when we run a given gate in ...

Find SimilarView on arXiv

Energy-Reliability Limits in Nanoscale Feedforward Neural Networks and Formulas

July 13, 2016

86% Match
Avhishek Chatterjee, Lav R. Varshney
Information Theory
Information Theory

Due to energy-efficiency requirements, computational systems are now being implemented using noisy nanoscale semiconductor devices whose reliability depends on energy consumed. We study circuit-level energy-reliability limits for deep feedforward neural networks (multilayer perceptrons) built using such devices, and en route also establish the same limits for formulas (boolean tree-structured circuits). To obtain energy lower bounds, we extend Pippenger's mutual information p...

Find SimilarView on arXiv

Principles of Low Dissipation Computing from a Stochastic Circuit Model

February 25, 2021

86% Match
Chloe Ya Gao, David T. Limmer
Statistical Mechanics
Chemical Physics

We introduce a thermodynamically consistent, minimal stochastic model for complementary logic gates built with field-effect transistors. We characterize the performance of such gates with tools from information theory and study the interplay between accuracy, speed, and dissipation of computations. With a few universal building blocks, such as the NOT and NAND gates, we are able to model arbitrary combinatorial and sequential logic circuits, which are modularized to implement...

Find SimilarView on arXiv