On reliable computation by noisy random Boolean formulas
classification
❄️ cond-mat.dis-nn
math.PR
keywords
formulasbooleancomputationboundgatesnoisenoisyrandom
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.