Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise
Rüdiger Reischuk · 1998
For ordinary circuits with a fixed upper bound on the maximal fanin of gates it has been shown that logarithmic redundancy is necessary and sufficient to overcome random hardware faults. Here, we consider the same question for unbounded fanin circuits that in the noiseless case can compute Boolean functions in sublogarithmic depth. In this case the details of the fault model become more important. One may assume that only gates, resp. only wires may deliver wrong values, or that both gates and wires may behave faulty due to random noise. The fault tolerance depends on the types of gates that are used, and whether the error probabilities are known exactly or only an upper bound for them. Concerning the first distinction the two most important models are circuits consisting of and- and or-gates with arbitrarily many inputs, and circuits built from the more general type of threshold gates. We will show that reliable computation is basically impossible for and/or--circuits and threshold ci...