Lower bounds for the complexity of reliable Boolean circuits with noisy gates
Péter Gács, Anna Gál · IEEE Transactions on Information Theory · 1994
Proves that the reliable computation of any Boolean function with sensitivity s requires /spl Omega/(s log s) gates if the gates fail independently with a fixed positive probability. This theorem was stated by Dobrushin and Ortyukov (1977), but their proof was found by Pippenger, Stamoulis, and Tsitsiklis (1991) to contain some errors.>