Title :
On the maximum tolerable noise for reliable computation by formulas
Author :
Evans, William ; Pippenger, Nicholas
Author_Institution :
Dept. of Comput. Sci., Arizona Univ., Tucson, AZ, USA
fDate :
5/1/1998 12:00:00 AM
Abstract :
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 ε is less than or greater than ε0=(3-√7)/4=0.08856…
Keywords :
Boolean functions; logic gates; noise; probabilistic logic; reliability theory; failure; formulas; maximum tolerable noise; noisy 2-input NAND gates; probability; reliable computation; Boolean algebra; Boolean functions; Computer science; Polynomials;
Journal_Title :
Information Theory, IEEE Transactions on
