We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least $\beta_2=(3-\sqrt{7})/4\approx 8.856\%$, fault-tolerant computation is not possible. On the other hand, if all gates fail with probability $\epsilon<\beta_2$ and $\epsilon$ is the same for all gates, then 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_2<\beta_2$ such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range $[0,\alpha_2]$.
Hence, while a hardware manufacturer who consistently produces bad gates with noise rate $\alpha_2$ can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most $\alpha_2$ cannot.
LaTeX errors in abstract on ECCC website corrected
We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least $\e=(3-\sqrt{7})/4\approx 8.856\%$, fault-tolerant computation is not possible. On the other hand, if all gates fail with probability $\epsilon<\e$ and $\epsilon$ is the same for all gates, then fault-tolerant computation is possible. The assumption that all gates fail with \emph{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_2<\e$ such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range $[0,\alpha_2]$.
Hence, while a hardware manufacturer who consistently produces bad gates with noise rate $\alpha_2$ can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most $\alpha_2$ cannot.
