Falk Unger, University of California, Berkeley
We consider fault-tolerant computation with formulas composed of noisy
Boolean gates with two input wires. It is known that if all gates
fail independently with probability at least beta (roughly equal to
8.856%), fault-tolerant computation is not possible. On the other
hand, if all gates fail with the same probability e and e
fault-tolerant computation is possible. The assumption that all gates
fail with "exactly" the same probability is pretty strong and
unrealistic in real-world scenarios. Furthermore, one might be tempted
to think that it can be removed easily, since making gates "better"
should not hurt. Surprisingly, this is not the case, as we show in
this work: there is a constant alpha
functions cannot be computed by formulas, if the noise rate of each
individual gate is selected adversarially in the range [0,alpha].
Hence, while a hardware manufacturer who produces consistently bad
gates with noise rate alpha can always achieve reliable computation, a
manufacturer who can only ensure that all gates have noise rates at
most alpha cannot.