Lemma 2.5.A p-random restriction p gives a subfunction fo of deg(f)sl with probability at least 1-M2-.Here p This can be proven by a similar argument as in the proof of Theorem 2.1;one just need to use Lemma 1.2 instead of Lemma 1.1.See [LMN93]for details. Proofof Theorem 2.2.Let u(p)be the distribution on (0,1)by setting each coordinate to be 1 with probability p.Let p=1/(10k(d-1)/d),I=pk/2=k/4/20.Note that we identify a string s E [0,1)n and a subset Ss[n]. ∑t:lekf()2≤2Es-u()s>pk/2f()] (Lemma 2.3) ≤2Es-up)[Pr[degf)>] (Lemma 2.4) ≤2M2-l (Lemma 2.5) 口 References [Has89]J.Hastad,Almost optimal lower bounds for small depth circuits,Advances in Computing Research,vol.5,pp.143-170,1989 Raz95]A.A.Razborov,Bounded arithmetics and lower bounds in boolean complexity, in Proceedings of Workshop on Feasible Mathematics II,1995 [LMN93]N.Linial,Y.Mansour,and N.Nisan,Constant depth circuits,Fourier transforms and learnability,Journal of the ACM,vol.40,pp.607-620,1993.Lemma 2.5. A p-random restriction 𝜌 gives a subfunction 𝑓𝜌 of deg(𝑓𝜌 ) ≤ 𝑙 with probability at least 1 − 𝑀2 −𝑙 . Here 𝑝 ≤ 1 10𝑑 𝑠 𝑑−1 . This can be proven by a similar argument as in the proof of Theorem 2.1; one just need to use Lemma 1.2 instead of Lemma 1.1. See [LMN93] for details. Proof of Theorem 2.2. Let 𝜇(𝑝) be the distribution on {0,1} 𝑛 by setting each coordinate to be 1 with probability 𝑝. Let 𝑝 = 1/(10𝑘 (𝑑−1)/𝑑 ), 𝑙 = 𝑝𝑘/2 = 𝑘 1/𝑑 /20. Note that we identify a string 𝑠 ∈ {0,1} 𝑛 and a subset 𝑆 ⊆ [𝑛]. ∑ 𝑓̂(𝑡) 2 𝑡:|𝑡|>𝑘 ≤ 2E𝑠←𝜇(𝑝) [∑ 𝑓̂(𝑡) 2 𝑡:|𝑡𝑆 |>𝑝𝑘/2 ] (Lemma 2.3) ≤ 2E𝑠←𝜇(𝑝) [Pr r [deg(𝑓𝑟 ) > 𝑙]] (Lemma 2.4) ≤ 2𝑀2 −𝑙 (Lemma 2.5) □ References [Has89] J. Hastad, Almost optimal lower bounds for small depth circuits, Advances in Computing Research, vol. 5, pp. 143–170, 1989. [Raz95] A. A. Razborov, Bounded arithmetics and lower bounds in boolean complexity, in Proceedings of Workshop on Feasible Mathematics II, 1995. [LMN93] N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transforms and learnability, Journal of the ACM, vol. 40, pp. 607–620, 1993