The complexity of a function is invariant, within a constant factor, over any choice of a finite and complete basis; this important result in Boolean circuit complexity permits us to state results without bothering about the underlying basis. Pippenger provides a general analogue to this theorem in the case where the gates in a circuit are unreliable. This paper is required reading for anyone working in circuit complexity.

The paper begins by introducing a new, more general probabilistic failure model for Boolean networks, called the &egr; -admissible failure model, and relating it to two earlier approaches, the &egr; -independent and &egr; -majorized failure models. Loosely speaking, a network N of unreliable gates ( &egr; , &dgr; )-computes a function f according to a failure model M if the probability, under any distribution in M with failure parameter &egr;, that N disagrees with f on a given input is at most &dgr;.

In the &egr; -independent failure model, first introduced by von Neumann, a network is assigned one probability distribution in which gate failures occur independently with probability &egr;. The &egr;-independent failure model is often used for negative results, that is, in giving conditions under which a network fails. The problem with this model is that if a network ( &egr; , &dgr; )-computes a function f, it does not follow that it will compute f more reliably if the failure parameter &egr; is reduced.

This problem is addressed by the &egr; -admissible failure model, in which gate failures are more closely tied to the state of the network. Although von Neumann hinted at it, credit for this notion rests with Pippenger. In the &egr;-admissible model, the probability that a gate i fails must be at most &egr; given any failure configuration of the “non-successors” of i.

Positive results, giving conditions under which the network operates correctly, are often found under the &egr;-majorized failure model. The &egr; -majorized failure distributions are those that can be produced by a demon from &egr; -independent failure distributions by deleting some failures.

In order to compare models, the author introduces the notion of stringency, wherein a failure model M is more stringent than another model M′ if M includes all the probability distributions of M′. The &egr; -independent failure model is less stringent than the &egr; -admissible model, which is in turn less stringent than the &egr; -majorized model. Reliable computations by a network under one model imply reliable computations by the same network under a less stringent model. Thus positive results for the &egr; -majorized model, and negative results for the &egr;-independent model, apply to the &egr; -admissible model.

The paper finishes with the proof of a very general theorem stating that, under the &egr; -admissible failure model (and some other reasonable conditions), the size and depth complexity of a function is invariant within a constant factor, regardless of both the choice of basis and the choice of failure parameter for the gates.