Noise Threshold for Universality of Two-Input Gates

It is known that $\epsilon$-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<\beta_2=(3-\sqrt{7})/4\approx 8.856\%$. In this paper it is shown that this bound is tight for formulas, by proving that gates with 2 inputs, in which each gate fails with probability at least $\beta_2$ cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is $\beta_2$. It is conjectured that the same threshold also holds for circuits.