0 / 33Bounds on Reliable Boolean FunctionComputation with Noisy Gates- R. L. Dobrushin & S. I. Ortyukov, 1977- N. Pippenger, 1985- P. G´acs & A. G´al, 1994Presenter: Da Wang6.454 Graduate Seminar in Area IEECS, MITOct. 5, 2011QuestionGiven a network of noisy logic gates, what is the redundancyrequired if we want to compute the a Boolean function reliably?noisy: gates produce the wrong output independently with errorprobability no more than ε.reliably: the value computed by the entire circuit is correct withprobability at least 1 − δredundancy:minimum #gates needed for reliable computation in noisy circuitminimum #gates needed for reliable computation in noiseless circuitInoisy/noiseless complexityImay depend on the function of interestIupper bound: achievabilityIlower bound: converse1 / 33Part ILower Bounds for the Complexity ofReliable Boolean Circuits with Noisy Gates2 / 33History of development3 / 33[Dobrushin & Ortyukov 1977]IContains all the key ideasIProofs for a few lemmas are incorrect[Pippenger & Stamoulis & Tsitsiklis 1990]IPointed out the errors in [DO1977]IProvide proofs for the case of computing the parity function[G´acs & G´al 1994]IFollow the ideas in [DO1977] and provide correct proofsIAlso prove some stronger resultsIn this talkWe will mainly follow the presentation in [G´acs & G´al 1994].Problem formulationSystem Model4 / 33Boolean circuit Ca directed acycic graphnode ∼ gateedge ∼ in/out of a gateGate ga function g : {0, 1}ng→ {0, 1}Ing: fan-in of the gateBasis Φa set of possible gate functionse.g., Φ = {AND, OR, XOR}complete basisfor circuit C: ΦCmaximum fan-in in C: n(ΦC)Assumptionseach gate g has constant numberof fan-ins ng.f can be represented bycompositions of gate functions inΦC.Problem formulationError models (ε, p)5 / 33Gate errorA gate fails if its output valuefor z ∈ {0, 1}ngis different fromg(z)gates fail independently withIfixed probability εused for lower bound proofIprobability at most εε ∈ (0, 1/2)Circuit errorC(x): random variable for outputof circuit C on input x.A circuit computes f with errorprobability at most p ifP [C(x) 6= f(x)] ≤ pfor any input x.Problem formulationSensitivity of a Boolean functionLet f : {0, 1}n→ {0, 1} be a Boolean function with binary input vectorx = (x1, x2, . . . , xn).Let xlbe a binary vector that differs from x only in the l-th bit, i.e.,xli=(xii 6= l¬xii = l.f is sensitive to the lth bit on x if f(xl) 6= f(x).Sensitivity of f on x: #bits in x that f is sensitive to.I“effecitive” input sizeSensitivity of f: maximum over all x.6 / 33Asymptotic notations7 / 33f(n) = O (g(n)):lim supn→∞f(n)g(n)< ∞,f(n) = Ω (g(n)):lim infn→∞f(n)g(n)≥ 1,f(n) = Θ (g(n)):f(n) = O (g(n))andf(n) = Ω (g(n))Main results8 / 33Theorem: number of gates for reliable computationILet ε and p be any constants such that ε ∈ (0, 1/2), p ∈ (0, 1/2).ILet f be any Boolean function with sensitivity s.Under the error model (ε, p), the number of gates of the curcuit is Ω (s log s).Corollary: redundancy of noisy computationFor any Boolean function of n variables and with O (n) noiseless complexityand Ω (n) sensitivity, the redundancy of noisy computation is Ω (log n).Ie.g., nonconstant symmetric function of n variables has redundancyΩ (log n)Equivalence result for wire failures9 / 33Lemma 3.1 in Dobrushin&OrtyukovILet ε ∈ (0, 1/2) and δ ∈ [0, ε/n(ΦC)].ILet y and t be the vector that a gate receives when the wire fail anddoes not fail respectively.For any gate g in the circuit C there exists unique values ηg(y, δ) such thatifIthe wires of C fails independently with error probability δ, andIthe gate g fails with probability ηg(y, δ) when receiving input y,then the probability that the output of g is different from g(t) is equal to ε.InsightsIndependent gate failures can be “simulated” by independently wirefailures and corresponding gate failures.These two failure modes are equivalent in the sense that the circuit Ccomputes f with the same error probability.“Noisy-wires” version of the main result10 / 33TheoremILet ε and p be any constants such that ε ∈ (0, 1/2), p ∈ (0, 1/2).ILet f be any Boolean function with sensitivity s.Let C be a circuit such thatIits wires fail independently with fixed probability δ, andIeach gate fails independently with probability ηg(y, δ) when receiving y.Suppose C computes f with error probability at most p. Then the numberof gates of the curcuit is Ω (s log s).Error analysisFunction and circuit inputs11 / 33Maximal sensitive set S for fs > 0: sensitivity of fz: an input vector with s bits that f is sensitive toIan input vector where f has maximum sensitivityS: the set of sensitive bits in zIkey objectBl: edges originated from l-th inputml, |Bl|e.g.Il = 3IBlIml= 31234f(z)Error analysisWire failures12 / 33For β ⊂ Bl, let H(β) be the event thatfor wires in Bl, only those in β fail.Letβl, arg maxβ⊂BlPC(zl) = f(zl)H(β) Ithe best failing set for input zlLet Hl, H(Bl\ βl)input lw1w2w3Bl= {w1, w2, w3}β = {w2}Fact 1P [C(z) 6= f(z) |Hl] = PC(zl) = f(zl)H(βl) ProofIf is sensitive to zlI¬zl⇔ “flip” all wires in Blβlis the worst non-failing set for input zError analysisError probability given wire failures13 / 33Fact 2PC(zl) = f(zl)H(βl) ≥ 1 − pProofIPC(zl) = f(zl) ≥ 1 − pIβlmaximizes PC(zl) = f(zl)H(β) Fact 1 & 2 ⇒ Fact 3For each l ∈ S,P [C(z) 6= f(z) |Hl] ≥ 1 − pwhere {Hl, l ∈ S} are independent events. Furthermore, Lemma 4.3 in[G´acs&G´al 1994] showsP"C(z) 6= f(z)[l∈SHl#≥ (1 −√p)2The error probability given HlorSl∈SHlis relatively large.Error analysisBounds on wire failure probabilities14 / 33Notep ≥ P [C(z) 6= f(z)]≥ P"C(z) 6= f(z)[l∈SHl#P"[l∈SHl#Fact 3 impliesFact 4P"[l∈SHl#≤p(1 −√p)2which implies (via Lemma 4.1 in [G´acs&G´al 1994]),Fact 5P"[l∈SHl#≥1 −p(1 −√p)2Xl∈SP [Hl]Error analysisBounds on the total number of sensitive wires15 / 33Fact 6P [Hl] = (1 − δ)|βl|δml−|βl|≥ δmlFact 4 & 5 ⇒p1 − 2√p≥Xl∈Sδml≥ s Yl∈Sδml!1/swhich leads toXl∈Sml≥slog(1/δ)logs1 − 2√pplower bound on the total number of “sensitive wires”Lower bound on number of gates16 / 33Let NCbe the total number of gates in C:n(ΦC)NC≥Xgng≥Xl∈Sml≥slog(1/δ)logs1 − 2√ppComments:The above proof is for p ∈ (0,