Reliability

• Invariance of complexity measures for networks with unreliable gates by Nicholas Pippenger, J. ACM, Vol. 36, Issue 3, pp. 531-539 (1989).
  Abstract: A new probabilistic failure model for networks of gates is formulated. Although this model has not been used previously, it supports the proofs of both the positive and negative results appearing in the literature. Furthermore, with respect to this new model, the complexity measures of both size and depth are affected by at most constant multiplicative factors when the set of functions that can be computed by gates is changed from one finite and complete basis to another, or when the bound on the failure probability of the gates is changed (within the limits allowed by the basis), or when the bound on the error probability of the network is changed (within the limits allowed by the basis and the failure probability of the gates).

• Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates by P´eter G´acs and Anna G´al, IEEE Trans. Information Theory, Vol. 40, pp. 579-583 (1994).
  Abstract: We prove that the reliable computation of any Boolean function with sensitivity s requires W(s log s) gates if the gates of the circuit fail independently with a xed positive probability. This theorem was stated by Dobrushin and Ortyukov in 1977, but their proof was found by Pippenger, Stamoulis and Tsitsiklis to contain some errors. We save the original structure of the proof of Dobrushin and Ortyukov, correcting two points in the probabilistic argument.

• Information Theory and Noisy Computation by William S. Evans, UC Bekeley PhD Thesis, TR-94-057 (1994).
  Abstract: The information carried by a signal unavoidably decays when the signal is corrupted by random noise. This occurs when a noisy channel transmits a message as well as when a noisy component performs computation. We first study this signal decay in the context of communication and obtain a tight bound on the decay of the information carried by a signal as it crosses a noisy channel. We then use this information theoretic result to obtain depth lower bounds in the noisy circuit model of computation defined by von Neumann. In this model, each component fails (produces 1 instead of 0 or vice-versa) independently with a fixed probability, and yet the output of the circuit should be correct with high probability. Von Neumann showed how to construct circuits in this model that reliably compute a function and are no more than a constant factor deeper than noiseless circuits for the function. Our result implies that such a multiplicative increase in depth is necessary for reliable computation. The result also indicates that above a certain level of component noise, reliable computation is impossible.

  We use a similar technique to lower bound the size of reliable circuits in terms of the noise and complexity of their components, and the sensitivity of the function they compute. Our bound is asymptotically equivalent to previous bounds as a function of sensitivity, but unlike previous bounds, its dependence on component noise implies that as this noise increases to 1/2, the size of reliable circuits must increase unboundedly. In all cases, the bound is strictly stronger than previous results.

  Using different techniques, we obtain the exact threshold for component noise, above which noisy formulas cannot reliably compute all functions. We obtained an upper bound on this threshold in studying the depth of noisy circuits. The fact that this bound is only slightly larger than the true threshold indicates the high precision of our information theoretic techniques.

• Reliable computation by Peter G´acs Book Chapter (2005).
  The chapter contains introductory material on probability theory, logic circuits, and reliable computation with unreliable gates.