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 help@cs.ubc.ca.