Signal propagation and noisy circuits

The information carried by a signal decays when the signal is corrupted by random noise. This occurs when a message is transmitted over a noisy channe l, as well as when a noisy component performs computation. We first study t his signal decay in the context of communication and obtain a tight bound o n the rate at which information decreases as a signal crosses a noisy chann el. We then use this information theoretic result to obtain depth lower bou nds in the noisy circuit model of computation defined by von Neumann, In th is model, each component fails (produces 1 instead of 0 or vice-versa) inde pendently with a fixed probability, and yet the output of the circuit is re quired to be correct with high probability. Von Neumann showed how to const ruct circuits in this model that reliably compute a function and are no mor e than a constant factor deeper than noiseless circuits for the function. W e provide a lower bound on the multiplicative increase in circuit depth nec essary for reliable computation, and an upper bound on the maximum level of noise at which reliable computation is possible. A preliminary version of this work appeared in the first author's thesis [1 ].