Title :
On Reliable Computation by Noisy Random Boolean Formulas
Author :
Mozeika, Alexander ; Saad, David
Author_Institution :
Non-Linearity & Complexity Res. Group, Aston Univ., Birmingham, UK
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 gate. We show that these gates can be used to compute any Boolean function reliably below the noise bound.
Keywords :
Boolean functions; majority-like gate; noise bound; noisy computation; noisy random Boolean formulas; randomly generated k-ary Boolean formulas; reliable computation; Boolean functions; Complexity theory; Equations; Logic gates; Noise; Noise measurement; Reliability; $epsilon $ -noise; ??-noise; Random Boolean formulas; reliable computation;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2014.2370638
