On networks of noisy gates
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 30-38
- https://doi.org/10.1109/sfcs.1985.41
Abstract
We show that many Boolean functions (including, in a certain sense, "almost all" Boolean functions) have the property that the number of noisy gates needed to compute them differs from the number of noiseless gates by at most a constant factor. This may be contrasted with results of von Neumann, Dobrushin and Ortyukov to the effect that (1) for every Boolean function, the number of noisy gates needed is larger by at most a logarithmic factor, and (2) for some Boolean functions, it is larger by at least a logarithmic factor.Keywords
This publication has 10 references indexed in Scilit:
- Expanders obtained from affine transformationsPublished by Association for Computing Machinery (ACM) ,1985
- Improvements of Winograd's result on computation in the presence of noise (Corresp.)IEEE Transactions on Information Theory, 1984
- Explicit constructions of graphs without short cycles and low density codesCombinatorica, 1982
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- Reliable Information Storage in Memories Designed from Unreliable Components*Bell System Technical Journal, 1968
- Low-Density Parity-Check CodesPublished by MIT Press ,1963
- Coding for Logical OperationsIBM Journal of Research and Development, 1962
- On Codes for Checking Logical OperationsIBM Journal of Research and Development, 1959
- Computation in the Presence of NoiseIBM Journal of Research and Development, 1958
- Complexity in Electronic Switching CircuitsIRE Transactions on Electronic Computers, 1956