On a Lower Bound for the Redundancy of Reliable Networks with Noisy Gates
ID
TR-90-13
Publishing date
May 1990
Abstract
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.