ECCC-Report TR10-164https://eccc.weizmann.ac.il/report/2010/164Comments and Revisions published for TR10-164en-usThu, 04 Nov 2010 20:55:21 +0200
Revision 1
| Better gates can make fault-tolerant computation impossible |
Falk Unger
https://eccc.weizmann.ac.il/report/2010/164#revision1We 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. Thu, 04 Nov 2010 20:55:21 +0200https://eccc.weizmann.ac.il/report/2010/164#revision1
Paper TR10-164
| Better gates can make fault-tolerant computation impossible |
Falk Unger
https://eccc.weizmann.ac.il/report/2010/164We 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. Thu, 04 Nov 2010 20:41:05 +0200https://eccc.weizmann.ac.il/report/2010/164