language: en

On the Maximum Tolerable Noise for Reliable Computation by Formulas

William Evans*
will@cs.arizona.edu
Department of Computer Science The University of Arizona
Tucson, AZ 85721-0077, USA
Nicholas Pippenger**
nicholas@cs.ubc.ca
Department of Computer Science The University of British Columbia
Vancouver, BC V6T 1Z4, Canada

Abstract: It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability ", then reliable computation can or cannot take place according as " is less than or greater than " 0 = (3 p

[* This research was supported by an NSERC Canada International Fellowship. ** This research was supported by an NSERC Research Grant.]

1. Introduction