Reliable computation by networks in the presence of noise

Lower bounds on the depth of Boolean networks that can compute reliably in the presence of randomly occurring failures are proved. A bound is also given on the reliability that error-tolerant networks can achieve: this bound implies a limit strictly smaller than 1/2 on the failure probability per gate that can be tolerated. The results improve upon recently published bounds of N. Pippenger (ibid., vol.IT-34, p.194-7, 1988) on the depth of error-tolerant formulas and extend the bounds to the case of reliable computation by networks.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>