Noise threshold for universality of 2-input gates
Abstract
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.
International Symposium on Information Theory, 2007, minor corrections in v2
International Symposium on Information Theory, 2007, minor corrections in v2