Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-070 | 7th December 1998 00:00

Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?


Authors: RĂ¼diger Reischuk
Publication: 8th December 1998 09:46
Downloads: 1992


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/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 such circuits with unknown error probabilities.
Gates with large fanin are of no use in this case.
Circuits of arbitrary size, but fixed depth can compute
only a tiny subset of all Boolean functions reliably.

Only in case of threshold circuits and exactly known error probabilities
redundancy is able to compensate faults.
We describe a transformation from fault-free to fault-tolerant circuits
that is optimal with respect to depth keeping the circuit size polynomial.

ISSN 1433-8092 | Imprint