On Reliable Computation by Noisy Random Boolean Formulas

DOI10.1109/TIT.2014.2370638zbMATH Open1359.94937arXiv1206.4851OpenAlexW1979056074MaRDI QIDQ2978844

Alexander Mozeika, D. Saad

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We study noisy computation in randomly generated k-ary Boolean formulas. We establish bounds on the noise level above which the results of computation by random formulas are not reliable. This bound is saturated by formulas constructed from a single majority-like gates. We show that these gates can be used to compute any Boolean function reliably below the noise bound.

Full work available at URL: https://arxiv.org/abs/1206.4851

Mathematics Subject Classification ID

Fuzzy sets and logic (in connection with information, communication, or circuits theory) (94D05)

Related Items (1)

Improvements of Winograd's result on computation in the presence of noise (Corresp.)

Recommendations

• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• On the maximum tolerable noise of k-input gates for reliable computation by formulas 👍 👎
• Reliable computation by formulas in the presence of noise 👍 👎
• Lower bounds for the complexity of reliable Boolean circuits with noisy gates 👍 👎
• On the maximum tolerable noise for reliable computation by formulas 👍 👎
• On the maximum tolerable noise for reliable computation by formulas 👍 👎

This page was built for publication: On Reliable Computation by Noisy Random Boolean Formulas