Lecture 10.Circuit Complexity 2 In last lecture we proved exponential lower bound for depth-3 circuit.The method doesn't extend to larger depth.In this lecture,we show how to prove exponential lower bounds for constant-depth circuits. 1.DNF,CNF,and Switching Lemma Recall: CNF:f)=where each is a literal,and each V is a clause. The function f is called a k-CNF if each ki s k. DNF:f(-Vwhere each is a monomial.The function f is called a k-DNF if each ki k. In general,a k-CNF is not necessarily also a k-DNF.For example,the AND function is a 1-CNF,but an n-DNF.The Switching Lemma says that if we fix some variables of a t-CNF, then we obtain a subfunction which is an s-DNF for some small s.We can actually use a random restriction.A p-random restriction makes each bit unfixed with probability p,and fixed with probability 1-p.In the latter case,the bit is fixed to be 0 or 1 each equal probability.We use p to denote a random restriction,and fo the resulting subfunction.The following lemma was given by Hastad [Has89]. Lemma 1.1.If f is a t-CNF,and p is a p-random restriction,then Pr[fo can be written as an s-DNF]1-(5pt)s. The original proof uses probabilistic arguments.Also see Razborov's elegent proof [Raz95] using a combinatorial method. Recall that deg(f)is the degree of the function represented as a polynomial in x,,n over R.Equivalently,it is the largest max{ISl:f(s)0}where the numbers f(s)are the Fourier coefficients.Lecture 10. Circuit Complexity 2 In last lecture we proved exponential lower bound for depth-3 circuit. The method doesn’t extend to larger depth. In this lecture, we show how to prove exponential lower bounds for constant-depth circuits. 1. DNF, CNF, and Switching Lemma Recall: CNF: 𝑓(𝑥1 … 𝑥𝑛 ) = ⋀ ⋁ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 𝑚 𝑖=1 , where each 𝑙 𝑖𝑗 is a literal, and each ⋁ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 is a clause. The function 𝑓 is called a 𝑘-CNF if each 𝑘𝑖 ≤ 𝑘. DNF: 𝑓(𝑥1 … 𝑥𝑛 ) = ⋁ ⋀ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 𝑚 𝑖=1 , where each ⋀ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 is a monomial. The function 𝑓 is called a 𝑘-DNF if each 𝑘𝑖 ≤ 𝑘. In general, a 𝑘-CNF is not necessarily also a k-DNF. For example, the AND function is a 1-CNF, but an n-DNF. The Switching Lemma says that if we fix some variables of a t-CNF, then we obtain a subfunction which is an s-DNF for some small s. We can actually use a random restriction. A p-random restriction makes each bit unfixed with probability p, and fixed with probability 1 − 𝑝. In the latter case, the bit is fixed to be 0 or 1 each equal probability. We use ρ to denote a random restriction, and 𝑓𝜌 the resulting subfunction. The following lemma was given by Hastad [Has89]. Lemma 1.1. If 𝑓 is a 𝑡-CNF, and ρ is a p-random restriction, then 𝐏𝐫[𝑓𝜌 can be written as an 𝑠-DNF] ≥ 1 − (5𝑝𝑡) 𝑠 . The original proof uses probabilistic arguments. Also see Razborov’s elegent proof [Raz95] using a combinatorial method. Recall that deg(𝑓) is the degree of the function represented as a polynomial in 𝑥1 ,…, 𝑥𝑛 over R. Equivalently, it is the largest max{|S|: 𝑓̂(𝑠) ≠ 0} where the numbers 𝑓̂(𝑠) are the Fourier coefficients