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 gates. We show that these gates can be used to compute any Boolean function reliably below the noise bound.
Bio: Alexander Mozeika is a post-doctoral researcher at the Finnish Centre of Excellence in Computational Inference and Aalto University. He obtained his PhD in Applied Mathematics from the King's College London and before moving to Finland was a Research Fellow at the Non-linearity and Complexity Research Group in Birmingham. His research interests are equilibrium and non-equilibrium statistical physics of disordered systems and its interdisciplinary applications (spin models, random boolean networks, fault tolerant computation, combinatorial optimization problems).
Host: Pekka Orponen
Last updated on 6 Nov 2012 by Sohan Seth - Page created on 5 Nov 2012 by Sohan Seth