The relative
computing power of these different architectures should be revisited to
incorporate the limitations imposed by noise. This will be particularly
relevant to future integrated circuits that rely on ever growing
gatedensities, which give rise to higher noise levels and probability of
production errors.
Von Neumann was the first to consider the problem of noisy computing,
aiming to better understand biological neural networks. He studied the
limitations imposed by faults in the fundamental elements of circuits and
demonstrated a method to correct their result. His analysis was followed by
more recent studies, which show that in the case of Boolean functions there
exists a limit for the tolerable gate noise; and that increased noise tolerance
requires circuits of greater depth.
We will use
established methods of statistical mechanics as well as new tools in the study
of noisy computation, which enable one to obtain
typical results for
whole
largescale Boolean functions comprising unreliable logical gates by mapping
them onto the corresponding physical system. The new approach will extend
existing worstcase and potentially loose bounds, derived using current
methodology, which is typically based on the properties of
local substructures. We therefore expect to obtain results that are
more relevant and representative, and are of both theoretical and practical
value.
Project objectives
 to
formalise the relation between typical random Boolean functions and the theory
and techniques of statistical mechanics;
 derive the
number of nontrivial Boolean functions in randomly constructed trees;
 analyse the
role of noise in random Boolean functions for both thermal noise and random
production errors;
 analyse
asymptotic errorrates below the critical gatenoise limits;
 and employ
advanced message passing techniques to obtain improved, more robust,
realisations in specific instances.
The principal
investigator of this project is Prof David Saad
Research fellow: Dr
Alexander Mozeika
Funding

Funding source: The Leverhulme Trust (F/00 250/H)

Funding amount: £ 135,111

Duration: 1/200912/2011
Achievements
Publications
Journal papers
 A.
Mozeika, D. Saad and J. Raymond, “Computing with Noise  Phase Transitions in Boolean Formulas”, Phys. Rev. Lett. 103,
248701 (2009).
 A.
Mozeika, D. Saad and J. Raymond, “Noisy Random Boolean Formulae  a StatisticalPhysics Perspective”, Phys. Rev. E 82, 041112 (2010).
 A.
Mozeika and D. Saad, “Dynamics of Boolean Networks  an Exact Solution”, Phys.
Rev. Lett. 106, 214101
(2011).
 A.
Mozeika and D. Saad, “Phase Transitions and Memory Effects in the Dynamics of BooleanNetworks”, Philosophical Magazine, 92, Issue 13, 210229,
(2012).
 D.
Saad and A. Mozeika, “Islands of equilibrium in a dynamical world”, submitted
(2012).
 A.
Mozeika and D. Saad, “Growing Boolean functions in the presence of noise”, submitted (2012).
A. Mozeika and D. Saad, “On the Computational Ability of Boolean
Circuits”, in preparation (2011).
Conferences proceedings
 A.
Mozeika, D. Saad and J. Raymond, On the Robustness of Random BooleanFormulae, Proceedings of the International Workshop on
StatisticalMechanical Informatics 2010 (IWSMI2010), Journal of Physics:
Conference Series 233 (2010) 012015.
Presentations  oral
 A. Mozeika, D. Saad and J. Raymond, Computing
with noise  a statistical physics approach, Techniques and Challenges from
Statistical Physics, Centre de Recerca Matematica Bellaterra, Spain, 1416
October, 2009.
 A. Mozeika, D. Saad and J. Raymond, On
the Robustness of Random Boolean Formulae, the International Workshop on
statisticalMechanical Informatics 2010 (IWSMI2010) March 710, 2010, Kyoto,
Japan.*
 A. Mozeika, D. Saad and J. Raymond, Statistical
Mechanics of Noisy Computation, Statistical physics of complexity,
optimization and systems biology, 712 March 2010, School of theoretical
physics, Les Houches, France.
 A. Mozeika, D. Saad and J. Raymond, Nonequilibrium
statistical mechanics of Noisy Computing, Nonequilibrium Statistical
physics of complex systems (Satellite Meeting of STATPHYS24), 2629 July 2010,
Seoul, South Korea.
 A. Mozeika and D. Saad, Dynamics of
Boolean Networks  an Exact Solution, Statistical physics of complexity,
optimization, and systems biology ,1418 February 2011 Bardonecchia, Italy. *
 A. Mozeika and D. Saad, Dynamics of
Boolean Networks  a Generating Functional Analysis, Interdisciplinary
Applications of Statistical Physics & Complex Networks,1 March 1 April
2011 Beijing. *
 A. Mozeika and D. Saad, Dynamics of
Boolean Networks  an exact solution, Miniconference on statistical
mechanics of glassy and disordered systems, 2324 May 2011, King’s College
London.
 A. Mozeika and D. Saad, , Exact
solution of Boolean dynamics with random connections, thermal noise and strong
memory effects, SigmaPhi2011 International Conferenceon Statistical
Physics, 1115 July 2011, Larnaka, Cyprus. (2011).

D.Saad and A. Mozeika, Islands of equilibrium in
nonequilibrium systems, Biology and Physics of Information Processing,
Nordita workshop, 16 April 11 May 2012, Stockholm (2012).*

A. Mozeika and D. Saad, On the existence of
equilibrium domains in nonequilibrium systems, Statistical Mechanics of
Unsatisfiability and Glasses, Mariehamn, Åland, Sweden
(2012)

D.Saad
and A. Mozeika, Equilibriumlike domains in nonequilibrium systems,
Machine Learning, August 2931 2012, the International Center for Theoretical
Physics in Trieste, Italy (2012).*

A. Mozeika and D.Saad, Phase transitions and memory effects in the dynamics of noisy Boolean
networks, Biology and Physics of Information Processing, Nordita workshop, 16
April 11 May 2012, Stockholm (2012).

D.Saad and A.
Mozeika, Equilibriumlike domains in
nonequilibrium systems, Machine Learning, September 1028 2012, The
MaxPlanck Institute for Complex Systems, Dresden, Germany (2012).*
*  By invitation
Presentation  poster
 A.
Mozeika, D. Saad and J. Raymond, Computing with Noise  Phase Transitions in
Boolean Formulas, European Conference on Complex Systems’ 09, University of
Warwick, 2125 September, 2009.