Title :
Lower bounds for the complexity of reliable Boolean circuits with noisy gates
Author :
Gács, Péter ; Gál, Anna
Author_Institution :
Dept. of Comput. Sci., Boston Univ., MA, USA
fDate :
3/1/1994 12:00:00 AM
Abstract :
Proves that the reliable computation of any Boolean function with sensitivity s requires Ω(s log s) gates if the gates fail independently with a fixed positive probability. This theorem was stated by Dobrushin and Ortyukov (1977), but their proof was found by Pippenger, Stamoulis, and Tsitsiklis (1991) to contain some errors
Keywords :
Boolean functions; circuit reliability; computational complexity; logic circuits; logic gates; network analysis; Boolean function; complexity; errors; noisy gates; reliable Boolean circuits; Boolean functions; Circuit noise; Circuits; Computer science; Gas insulated transmission lines; Information theory; Karhunen-Loeve transforms; Redundancy; Signal to noise ratio; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
