We now give another lemma. Lemma 1.2.Under the condition of Lemma 1.1, Pr[deg(fo)>s]<(5pt)s, 2.Application of Switching Lemma Recall that certificate complexity of a function f:(0.1)"{0,1}on an input x is C(f,x)=min {ISl:Ss [nl,f(y)=f(x)Vy with ys =xs} where xs=(xi:iE S).Further define Ci(f)=max {C(f,x):f(x)=13,Co(f)=max {C(f,x):f(x)=03, and C(f)=maxC(f,x),Cmin (f)=min C(f,x). To get familiar with the concept,consider some specific functions: AND:Co(f)=1,Ci(f)=n,C(f)=n,Cmin (f)=1. OR:Co(f)=n,Ci(f)=1,C(f)=n,Cmin(f)=1. Parity:Co(f)=n,Ci(f)=n,C(f)=n,Cmin(f)=n. Majority:Co(f)=n/2,C1(f)=n/2,C(f)=n/2,Cmin (f)=n/2. Theorem 2.1.Iffcan be computed by a depth-(d +1)circuit of size S,then 1 Cmin(月≤n(1-100og时+21ogs. Using the parameters for Parity,we immed iately get the following corollary. Corollary.If a circuit with depth d computes the Parity function,then the circuit size is at least S=2n(n4-1),We now give another lemma. Lemma 1.2. Under the condition of Lemma 1.1, 𝐏𝐫[deg(𝑓𝜌 ) > 𝑠] < (5𝑝𝑡) 𝑠 , 2. Application of Switching Lemma Recall that certificate complexity of a function 𝑓:{0.1} 𝑛 → {0,1} on an input 𝑥 is 𝐶(𝑓, 𝑥) = min {|𝑆|: 𝑆 ⊆ [𝑛],𝑓(𝑦) = 𝑓(𝑥) ∀𝑦 with 𝑦𝑆 = 𝑥𝑆 } where 𝑥𝑆 = (𝑥𝑖 :𝑖 ∈ 𝑆). Further define 𝐶1 (𝑓) = max {𝐶(𝑓, 𝑥):𝑓(𝑥) = 1}, 𝐶0 (𝑓) = max {𝐶(𝑓,𝑥): 𝑓(𝑥) = 0}, and 𝐶(𝑓) = max 𝑥 𝐶(𝑓, 𝑥) , 𝐶𝑚𝑖𝑛(𝑓) = min 𝑥 𝐶(𝑓, 𝑥) . To get familiar with the concept, consider some specific functions: ⚫ AND: 𝐶0 (𝑓) = 1, 𝐶1 (𝑓) = 𝑛, 𝐶(𝑓) = 𝑛, 𝐶𝑚𝑖𝑛 (𝑓) = 1. ⚫ OR: 𝐶0 (𝑓) = 𝑛, 𝐶1 (𝑓) = 1, 𝐶(𝑓) = 𝑛, 𝐶𝑚𝑖𝑛(𝑓) = 1. ⚫ Parity: 𝐶0 (𝑓) = 𝑛, 𝐶1 (𝑓) = 𝑛, 𝐶(𝑓) = 𝑛, 𝐶𝑚𝑖𝑛(𝑓) = 𝑛. ⚫ Majority: 𝐶0 (𝑓) = 𝑛/2, 𝐶1 (𝑓) = 𝑛/2, 𝐶(𝑓) = 𝑛/2,𝐶𝑚𝑖𝑛 (𝑓) = 𝑛/2. Theorem 2.1. If f can be computed by a depth-(𝑑 + 1) circuit of size S, then 𝐶𝑚𝑖𝑛(𝑓) ≤ 𝑛 (1 − 1 10𝑑(log 𝑆) 𝑑−1 ) + 2 log 𝑆. Using the parameters for Parity, we immediately get the following corollary. Corollary. If a circuit with depth d computes the Parity function, then the circuit size is at least 𝑆 = 2 𝛺(𝑛 𝑑−1 )