Publication | Closed Access
Lower bounds for the complexity of reliable Boolean circuits with noisy gates
80
Citations
11
References
1994
Year
Circuit ComplexityNoisy GatesEngineeringBoolean FunctionComputational Complexity TheoryVerificationReliable ComputationComputational ComplexityCommunication ComplexityFormal VerificationProof ComplexityDiscrete MathematicsLower BoundComputer ScienceProbability TheoryReliable Boolean CircuitsProbabilistic VerificationFormal MethodsFixed Positive ProbabilityLower Bounds
Proves that the reliable computation of any Boolean function with sensitivity s requires /spl Omega/(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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
| Year | Citations | |
|---|---|---|
Page 1
Page 1