Technical Reports

The ICICS/CS Reading Room

UBC CS TR-90-13 Summary

On a Lower Bound for the Redundancy of Reliable Networks with Noisy Gates, May 1990 Nicholas Pippenger, George D. Stamoulis and John N. Tsitsiklis

We prove that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a networks with noisy gates. This result is the same as one claimed by Dobrushin and Ortyukov in 1977, but the proof they gave appears to be incorrect.

If you have any questions or comments regarding this page please send mail to