Technical Reports

The ICICS/CS Reading Room

UBC CS TR-95-20 Summary

On the Maximum Tolerable Noise for Reliable Computation by Formulas, September 1995 William Evans and Nicholas Pippenger, 16 pages

It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability e, then reliable computation can or cannot take place according as e is less than or greater than e_0 = (3-sqrt(7))/4 = 0.08856....

If you have any questions or comments regarding this page please send mail to