Reliable computation with noisy circuits and decision trees-a general n log n lower bound

Boolean circuits in which gates independently make errors with probability (at most) ε are considered. It is shown that the critical number crit(f) of a function f yields lower bound Ω(crit(f) log crit (f)) for the noisy circuit size. The lower bound is proved for an even stronger computational model, static Boolean decision trees with erroneous answers. A decision tree is static if the questions it asks do not depend on previous answers. The depth of such a tree provides a lower bound on the number of gates that depend directly on some input and hence on the size of a noisy circuit. Furthermore, it is shown that an Ω(n log n) lower bound holds for almost all Boolean n-input functions with respect to the depth of noisy dynamic decision trees. This bound is the best possible and implies that almost all n-input Boolean functions have noisy decision tree complexity Θ(n log n) in the static as well as in the dynamic case