Now we sketch the proof for Theorem 2.1. Proofidea (of Theorem 2.1).Repeatedly apply the Switching Lemma,in a bottom up manner, to reduce the depth.Use the lemma with s =t =2log S,and p =1/10s.Once we replace a CNF by a DNF,we'll see two consecutive layers of OR gates,thus we can collapse these two layers.Each round leaves about p-fraction of variables unfixed,thus finally we get a depth-2 circuit which computes a subfunction g of pn=n/(10log S)1variables.We need some special handling for the first step,which can also be done as an application of the switching lemma.And finally the s-DNF function g can be made constant by restricting s variables.Thus overall we restrictedngvariables and obtained a constant function.By definition of Cmin(f),we get the claimed statement. Next we show exponential lower bounds for more general functions,superseding the previous result for Parity.It's interesting also because it links circuit complexity and Fourier coefficients.This famous result was given in [LMN93]. Theorem 2.2.If a circuit with depth d and size Mcomputes a function f:{0,1)m{-1,+1), then M≥2ak4.∑.f92. s:Isl>k Note that for Parity function,there is only one nonzero Fourier coefficient:f(1")=1.Thus we can take k=n-1 and obtain a lower bound of 2(n) We'll need a couple of lemmas to prove this theorem. Lemma2.3.∑t:f(t)2≤2Esup[Et:ltsl-pk/2f()2] Proof.Think of T also as a random variable distributed according to Fourier weights f(t)2 (We identify a string s E{0,1)m with a subset S[n].)Then RHS =2 Es[Pr[IT n SI >pk/2]]=2 Pr[IT nSI pk/2]Now we sketch the proof for Theorem 2.1. Proof idea (of Theorem 2.1). Repeatedly apply the Switching Lemma, in a bottom up manner, to reduce the depth. Use the lemma with 𝑠 = 𝑡 = 2log 𝑆, and 𝑝 = 1/10𝑠. Once we replace a CNF by a DNF, we’ll see two consecutive layers of OR gates, thus we can collapse these two layers. Each round leaves about p-fraction of variables unfixed, thus finally we get a depth-2 circuit which computes a subfunction 𝑔 of 𝑝 𝑑−1 𝑛 = 𝑛/(10log 𝑆) 𝑑−1 variables. We need some special handling for the first step, which can also be done as an application of the switching lemma. And finally the s-DNF function 𝑔 can be made constant by restricting 𝑠 variables. Thus overall we restricted 𝑛 − 𝑛 10𝑑 (log 𝑆)𝑑−1 + 2log 𝑆 variables and obtained a constant function. By definition of 𝐶𝑚𝑖𝑛(𝑓), we get the claimed statement. □ Next we show exponential lower bounds for more general functions, superseding the previous result for Parity. It’s interesting also because it links circuit complexity and Fourier coefficients. This famous result was given in [LMN93]. Theorem 2.2. If a circuit with depth d and size M computes a function 𝑓:{0,1} 𝑛 → {−1, +1}, then 𝑀 ≥ 2 Ω(𝑘 1/𝑑 ) ⋅ ∑ 𝑓̂(𝑠) 2 𝑠:|𝑠|>𝑘 . Note that for Parity function, there is only one nonzero Fourier coefficient: 𝑓̂(1 𝑛) = 1. Thus we can take 𝑘 = 𝑛 − 1 and obtain a lower bound of 2 Ω(𝑛 1/𝑑 ) . We’ll need a couple of lemmas to prove this theorem. Lemma 2.3. ∑ 𝑓̂(𝑡) 2 𝑡:|𝑡|>𝑘 ≤ 2E𝑠←𝜇(𝑝) [∑ 𝑓̂(𝑡) 2 𝑡:|𝑡𝑆 |>𝑝𝑘/2 ]. Proof. Think of T also as a random variable distributed according to Fourier weights 𝑓̂(𝑡) 2 . (We identify a string 𝑠 ∈ {0,1} 𝑛 with a subset 𝑆 ⊆ [𝑛].) Then RHS = 2 E𝑆 [Pr 𝑇 [|𝑇 ∩ 𝑆| > 𝑝𝑘/2]] = 2 Pr 𝑆,𝑇 [|𝑇 ∩ 𝑆| > 𝑝𝑘/2]