Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Applied Mathematics
On A Lower Bound For The Redundancy Of Reliable Networks With Noisy Gates, Nicholas Pippenger
On A Lower Bound For The Redundancy Of Reliable Networks With Noisy Gates, Nicholas Pippenger
All HMC Faculty Publications and Research
A proof is provided that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a network with noisy gates. This result was first stated by R.L. Dobrushin and S.I. Ortyukov (1977). However, the authors believe that the analysis given by Dobrushin and Ortyukov is not entirely correct. The authors establish the result by following the same steps and by replacing the questionable part of their analysis with entirely new arguments.
Reliable Computation By Formulas In The Presence Of Noise, Nicholas Pippenger
Reliable Computation By Formulas In The Presence Of Noise, Nicholas Pippenger
All HMC Faculty Publications and Research
It is shown that if formulas are used to compute Boolean functions in the presence of randomly occurring failures then: (1) there is a limit strictly less than 1/2 to the failure probability per gate that can be tolerated, and (2) formulas that tolerate failures must be deeper (and, therefore, compute more slowly) than those that do not. The heart of the proof is an information-theoretic argument that deals with computation and errors in very general terms. The strength of this argument is that it applies with equal ease no matter what types of gate are available. Its weaknesses is …