Invariance of complexity measures for networks with unreliable gates

DOI10.1145/65950.77248zbMath0677.94018OpenAlexW1967313757MaRDI QIDQ3834001

Nicholas J. Pippenger

Publication date: 1989

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/65950.77248

zbMATH Keywords

verificationreliabilityerror probabilitycomplexity measuresgatesself-correcting networks

Mathematics Subject Classification ID

Related Items

Computing Boolean functions from multiple faulty copies of input bits, On the design of reliable Boolean circuits that contain partially unreliable gates, Fault tolerance in cellular automata at high fault rates, On the computational power of probabilistic and faulty neural networks, FAULT-TOLERANT NANOCOMPUTERS BASED ON ASYNCHRONOUS CELLULAR AUTOMATA, Can large fanin circuits perform reliable computations in the presence of faults?, Stochastic analog networks and computational complexity, Effective theories for circuits and automata