Noise threshold for universality of 2-input gates
| dc.creator | Unger, Falk | |
| dc.date | 2007-11-02 | |
| dc.date | 2008-09-06 | |
| dc.date.accessioned | 2026-07-07T10:00:45Z | |
| dc.date.available | 2026-07-07T10:00:45Z | |
| dc.description | Evans and Pippenger showed in 1998 that noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability epsilon and epsilon<theta, where theta is roughly 8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least theta cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is theta. We conjecture that the same threshold also holds for circuits. | |
| dc.description | International Symposium on Information Theory, 2007, minor corrections in v2 | |
| dc.identifier | https://arxiv.org/abs/0711.0351 | |
| dc.identifier | http://arxiv.org/abs/0711.0351 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168413 | |
| dc.subject | Information Theory | |
| dc.subject | Computational Complexity | |
| dc.title | Noise threshold for universality of 2-input gates | |
| dc.type | text |