香港中文大学：《Theory of Computational Complexity》课程教学资源（讲义）Lecture 9 Circuit Complexity

Lecture 9.Circuit Complexity From this lecture we start to prove lower bounds in the circuit model.As we said,the task is too hard for general circuits.So people studied special types of circuits.One important class contains circuits with small depth Recall that a circuit is a DAG with each node associated with a gate that computes a basic function,such as AND,OR and NOT.The fanin of a gate can be arbitrary.(Namely,the AND and OR gates are not just binary.)We will draw a circuit in the top-down manner,s.t. the output gate is the top layer and gates in the bottom layer connect to the input variables. 1.Depth 2:DNF and CNF This section considers depth-2 circuits.If the top gate is AND,then the circuit is essentially a CNF or DNF.Recall: CNF(conjunctive normal form):f)=where each lij is either a variable or the negation ofa variable.Each is called airand eachisa called a clause. DNF (Disjunetive normal fomm):f)=Vwhere each is alieral,and eachisacalled a monomial. Any function can be written as a CNF and DNF.(Convince yourself.)We'd like to find an explicit function f s.t.if we write it as a CNF or DNF,then the number of clauses/monomials is very large.Such a function is not hard to find,actually the Parity function serves as such an example.(Recall:Parity(x)=..xn) Theorem 1.1.Any depth-2 circuit that computes Parity needs at least 2-1gates. Can you figure out a proof?(It's not complicated;only one or two lines.And it'll be used later.)

Lecture 9. Circuit Complexity From this lecture we start to prove lower bounds in the circuit model. As we said, the task is too hard for general circuits. So people studied special types of circuits. One important class contains circuits with small depth. Recall that a circuit is a DAG with each node associated with a gate that computes a basic function, such as AND, OR and NOT. The fanin of a gate can be arbitrary. (Namely, the AND and OR gates are not just binary.) We will draw a circuit in the top-down manner, s.t. the output gate is the top layer and gates in the bottom layer connect to the input variables. 1. Depth 2: DNF and CNF This section considers depth-2 circuits. If the top gate is AND, then the circuit is essentially a CNF or DNF. Recall: CNF (conjunctive normal form): 𝑓(𝑥1 … 𝑥𝑛 ) = ⋀ ⋁ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 𝑚 𝑖=1 , where each 𝑙 𝑖𝑗 is either a variable or the negation of a variable. Each 𝑙 𝑖𝑗 is called a literal, and each ⋁ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 is a called a clause. DNF (Disjunctive normal form): 𝑓(𝑥1 … 𝑥𝑛 ) = ⋁ ⋀ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 𝑚 𝑖=1 , where each 𝑙 𝑖𝑗 is a literal, and each ⋀ 𝑙 𝑖𝑗 𝑘𝑖 𝑗=1 is a called a monomial. Any function can be written as a CNF and DNF. (Convince yourself.) We’d like to find an explicit function 𝑓 s.t. if we write it as a CNF or DNF, then the number of clauses/monomials is very large. Such a function is not hard to find, actually the Parity function serves as such an example. (Recall: Parity(𝑥) = 𝑥1 ⊕ …⊕ 𝑥𝑛 .) Theorem 1.1. Any depth-2 circuit that computes Parity needs at least 2 n−1 gates. Can you figure out a proof? (It’s not complicated; only one or two lines. And it’ll be used later.)

2.Depth 3 Now we consider depth-3 circuits.If the top gate of a circuit is AND,then we call it a I3-circuit. Let's first prove that if the circuit has a small top fanin,then it has to have a large size. Theorem 2.1.([Tsa01])If a IIa-circuit computing the Parity function has fanout 1 and top fanin t,then it has at least t2(/AND gates at the bottom layer. Proof.The idea is to switch the AND and OR of the two top layers using de Morgan rule,and then the problem is reduced to the depth 2 case.Suppose that the i-th OR gate on the middle layer has fanin si.Let hii be the j-th AND of the i-th OR gate of the top AND gate.Use de Morgan rule,we can change the depth-3 circuit to a depth-2 one,which has the top gate OR with fanin sS2...5.Note that each AND can accept at most one input,so sS2S 2n-1.Since each gate has fanout 1,the number of AND dates at the bottom layer is S1+S2+…+sn≥t(s1S2…s)1/≥t2(n-1)/r From the bound,you can see that when t is large,then we need new method.Next we introduce the k-limit method Suppose that Af-1(1)and Bf-1(0).An input y E A is a lower k-limit for B if for any S [m],ISI =k,there is an input xE B s.t.xs=ys and xsy.Recall that xsy means each xi≤yi, We will use the concept to prove an exponential lower bound for(the negation of)Majority. Formally,define Majn (x)=1 iffx+..+xn <n/2. The result was proved in [HJP95]. Theorem 2.2.Any II3-circuit computing theMajn function needs 2 fanout. Proof.The parameters in the following proof: n Vm m=7+rr=- 4 k=2vm

2. Depth 3 Now we consider depth-3 circuits. If the top gate of a circuit is AND, then we call it a Π3 -circuit. Let’s first prove that if the circuit has a small top fanin, then it has to have a large size. Theorem 2.1. ([Tsa01]) If a Π3 -circuit computing the Parity function has fanout 1 and top fanin 𝑡, then it has at least 𝑡2 (𝑛−1)/𝑡 AND gates at the bottom layer. Proof. The idea is to switch the AND and OR of the two top layers using de Morgan rule, and then the problem is reduced to the depth 2 case. Suppose that the i-th OR gate on the middle layer has fanin 𝑠𝑖 . Let ℎ𝑖𝑗 be the 𝑗-th AND of the 𝑖-th OR gate of the top AND gate. Use de Morgan rule, we can change the depth-3 circuit to a depth-2 one, which has the top gate OR with fanin 𝑠1 𝑠2 … 𝑠𝑡 . Note that each AND can accept at most one input, so 𝑠1 𝑠2 …𝑠𝑡 ≥ 2 𝑛−1 . Since each gate has fanout 1, the number of AND dates at the bottom layer is 𝑠1 + 𝑠2 + ⋯ + 𝑠𝑛 ≥ 𝑡(𝑠1 𝑠2 … 𝑠𝑡 ) 1/𝑡 ≥ 𝑡2 (𝑛−1)/𝑡 . □ From the bound, you can see that when t is large, then we need new method. Next we introduce the k-limit method. Suppose that 𝐴 ⊆ 𝑓 −1 (1) and 𝐵 ⊆ 𝑓 −1 (0). An input 𝑦 ∈ 𝐴 is a lower k-limit for B if for any 𝑆 ⊆ [𝑚], |𝑆| = 𝑘, there is an input 𝑥 ∈ 𝐵 s.t. 𝑥𝑆 = 𝑦𝑆 and 𝑥 ≤ 𝑦. Recall that 𝑥 ≤ 𝑦 means each 𝑥𝑖 ≤ 𝑦𝑖 . We will use the concept to prove an exponential lower bound for (the negation of) Majority. Formally, define ¬Maj𝑛 (𝑥) = 1 iff 𝑥1 + ⋯ + 𝑥𝑛 < 𝑛/2. The result was proved in [HJP95]. Theorem 2.2. Any Π3 -circuit computing the ¬Maj𝑛 function needs 𝑙 ≥ 2 Ω(√𝑛) fanout. Proof. The parameters in the following proof: 𝑚 = 𝑛 2 + 𝑟, 𝑟 = √𝑚 4 , 𝑘 = 2√𝑚

Solving it gives the following approximation: Vn/2 4 r≈Vn/2 4 k≈2√n/2. We need to define two sets: A={x∈{0,1m:lx|kasF≤(（白)e then there is a T[n]with IT'l =n-m to intersect all SE F. Proof.Since each SE F has size more than k,at least one xi,belong to at least k/n fraction of sets in F.Put it in T.Remove those sets SE F containing xi,.This leaves (1- k/n)fraction of F.Continue this.We claim that n-m steps kill all S E F.Indeed, a=(-91-名)-(1-m本)

Solving it gives the following approximation: 𝑚 ≈ 𝑛 2 + √𝑛/2 4 , 𝑟 ≈ √𝑛/2 4 , 𝑘 ≈ 2√𝑛/2. We need to define two sets: 𝐴 = {𝑥 ∈ {0,1}𝑚: |𝑥| 𝑘} has |𝐹| ≤ ( 𝑛 𝑚 ) 𝑘/2 , then there is a 𝑇 ⊆ [𝑛] with |𝑇| = 𝑛 − 𝑚 to intersect all 𝑆 ∈ 𝐹. Proof. Since each 𝑆 ∈ 𝐹 has size more than k, at least one 𝑥𝑖1 belong to at least 𝑘/𝑛 fraction of sets in F. Put it in T. Remove those sets 𝑆 ∈ 𝐹 containing 𝑥𝑖1 . This leaves (1 − 𝑘/𝑛) fraction of F. Continue this. We claim that 𝑛 − 𝑚 steps kill all 𝑆 ∈ 𝐹. Indeed, 𝛼 = (1 − 𝑘 𝑛 ) (1 − 𝑘 𝑛 − 1 )… (1 − 𝑘 𝑚 + 1 )

exp(-k(Hn-Hm)) (月” canceling the upper bound of F in the assumption of the lemma. To use this lemma,we take F to be the collection of bottom AND gates with more than k negated variables.By the lemma,there is a T[n]intersecting all of them.Set all variables in T to be 1,then these AND gates are eliminated.Thus each of the remaining AND gates contains at most k negated variables. Lemma 2.4.Suppose that we have a IIa-circuit computing f,with top fanin at most l and each bottom AND gate having at most k negated variables.Then there is an OR gate g in the middle level s.t.the set Bg={x∈{0,1}m:lx=r,g(x)=0} has mand B does not have any lower k-limit in 4. Proof.Recall the set B={x∈{0,1m:lx|=r}. Note that BB f-1(0).Since the top gate is AND,there is at least one OR gate in the middle level evaluating to 0 for inputs in B.Thus there is an OR gate g s.t. g1≥() Suppose the set has a lower k-limit yEA,namely g(y)=1 and for any Ss[m],ISI=k, there is an input xEB s.t.xs=ys.Consider each AND gateh feeding in g: n=AA

≤ 𝑒𝑥𝑝(− 𝑘 𝑛 − 𝑘 𝑛 − 1 − ⋯ − 𝑘 𝑚 + 1 ) = 𝑒𝑥𝑝(−𝑘(𝐻𝑛 − 𝐻𝑚)) ≤ ( 𝑛 𝑚 ) −𝑘/2 canceling the upper bound of |𝐹| in the assumption of the lemma. □ To use this lemma, we take F to be the collection of bottom AND gates with more than k negated variables. By the lemma, there is a 𝑇 ⊆ [𝑛] intersecting all of them. Set all variables in T to be 1, then these AND gates are eliminated. Thus each of the remaining AND gates contains at most k negated variables. Lemma 2.4. Suppose that we have a Π3 -circuit computing 𝑓, with top fanin at most 𝑙 and each bottom AND gate having at most k negated variables. Then there is an OR gate 𝑔 in the middle level s.t. the set 𝐵𝑔 ′ = {𝑥 ∈ {0,1}𝑚 : |𝑥| = 𝑟, 𝑔(𝑥) = 0} has |𝐵𝑔 ′ | ≥ ( 𝑚 𝑟 ) /𝑙 and 𝐵𝑔 ′ does not have any lower k-limit in A. Proof. Recall the set 𝐵 = {𝑥 ∈ {0,1}𝑚 : |𝑥| = 𝑟}. Note that 𝐵𝑔 ′ ⊆ 𝐵 ⊆ 𝑓 −1 (0). Since the top gate is AND, there is at least one OR gate in the middle level evaluating to 0 for inputs in B. Thus there is an OR gate 𝑔 s.t. |𝐵𝑔 ′ | ≥ ( 𝑚 𝑟 ) /𝑙. Suppose the set has a lower k-limit 𝑦 ∈ 𝐴, namely 𝑔(𝑦) = 1 and for any 𝑆 ⊆ [𝑚], |𝑆| = 𝑘, there is an input 𝑥 ∈ 𝐵𝑔 ′ s.t. 𝑥𝑆 = 𝑦𝑆 . Consider each AND gate h feeding in 𝑔: ℎ(𝑥) = ⋀𝑥̅𝑖 𝑖∈𝑆 ∧⋀𝑥𝑗 𝑗∈𝑇

We claim that h(y)=0.Indeed,since h(x)=0,there is an ;=0 or an xi=1.If the former,then yjxj=0 and thus h(y)=0.Ifthe latter,then since xs=ys,wealso have yi=xi=1,which again implies that h(y)=0. Since this holds for each h,we know that g(y)=0 as well,violating the assumption that yEA.▣ Lemma 2.5.For any set B'{x E {0,1)m:xl=r}with IB'l k",there is a lower k-limit y∈A for B'. Proof.Induction on r. r=1:0mE A is a lower k-limit for B'.First,it is lower to any other vector,namely 0ms x for any x.Second,for any S [m]with ISl =k,since IB'l>k when r =1,we have some element x E B's.t.the only 1 in x is not in S.This element serves the lower k-limit definition. Assuming r-1,consider r:If 0mEA is not a lower k-limit for B',then there is a set S [m]with ISl=ks.t.every x∈B'has at least one 1 in S.Take the most“popular'”i∈S at which at least 1/k fraction of B'have 1 at i-th position.Call the set of these elements C'B'.Flip these 1 to 0 and call the resulting set D',then they each have r-1 ones.Note that Use induction hypothesis to getaywith less than 1 ones s.t.y is lower k-limit for D'.Note that y:=0 since y is lower than an element in D'. Flip yi to 1,and this element y'E A since ly'l=lyl<r-1+1=r.We claim that this y'is a lower k-limit for B'.The"lower"part is easy.For the"k-limit"part:for any T[m] with ITl =k,there is a xED'with y<x and yr=x7.Note that flipping the i-th bit from 0 to 1 makes y to y',and also make D'to C'B'.This implies that y=x where xis the string obtained fromx by flipping the i-th bit.Note thatC'B'.Thus y'is a lower k-limit for B

We claim that ℎ(𝑦) = 0. Indeed, since ℎ(𝑥) = 0, there is an 𝑥𝑗 = 0 or an 𝑥𝑖 = 1. If the former, then 𝑦𝑗 ≤ 𝑥𝑗 = 0 and thus ℎ(𝑦) = 0. If the latter, then since 𝑥𝑆 = 𝑦𝑆 , we also have yi = 𝑥𝑖 = 1, which again implies that ℎ(𝑦) = 0. Since this holds for each h, we know that 𝑔(𝑦) = 0 as well, violating the assumption that 𝑦 ∈ 𝐴. □ Lemma 2.5. For any set 𝐵 ′ ⊆ {𝑥 ∈ {0,1}𝑚 : |𝑥| = 𝑟} with |𝐵 ′ | > 𝑘 𝑟 , there is a lower k-limit 𝑦 ∈ 𝐴 for 𝐵’. Proof. Induction on 𝑟. 𝑟 = 1: 0 𝑚 ∈ A is a lower k-limit for 𝐵’. First, it is lower to any other vector, namely 0 𝑚 ≤ 𝑥 for any x. Second, for any 𝑆 ⊆ [𝑚] with |𝑆| = 𝑘, since |𝐵 ′ | > 𝑘 when 𝑟 = 1, we have some element 𝑥 ∈ 𝐵′ s.t. the only 1 in x is not in 𝑆. This element serves the lower k-limit definition. Assuming 𝑟 − 1, consider 𝑟: If 0 𝑚 ∈ A is not a lower k-limit for 𝐵’, then there is a set 𝑆 ⊆ [𝑚] with |𝑆| = 𝑘 s.t. every 𝑥 ∈ 𝐵′ has at least one 1 in 𝑆. Take the most “popular” 𝑖 ∈ 𝑆 at which at least 1/𝑘 fraction of 𝐵′ have 1 at i-th position. Call the set of these elements 𝐶 ′ ⊆ 𝐵′. Flip these 1 to 0 and call the resulting set 𝐷′, then they each have 𝑟 − 1 ones. Note that |𝐷 ′ | = |𝐶 ′ | ≥ |𝐵 ′ | 𝑘 > 𝑘 𝑟−1 . Use induction hypothesis to get a 𝑦 ∈ 𝐴 with less than 𝑟 − 1 ones s.t. y is lower k-limit for 𝐷’. Note that 𝑦𝑖 = 0 since y is lower than an element in 𝐷′. Flip 𝑦𝑖 to 1, and this element 𝑦 ′ ∈ 𝐴 since |𝑦 ′ | = |𝑦| < 𝑟 − 1 + 1 = 𝑟. We claim that this 𝑦′ is a lower k-limit for 𝐵′. The “lower” part is easy. For the “k-limit” part: for any 𝑇 ⊆ [𝑚] with |𝑇| = 𝑘, there is a 𝑥 ∈ 𝐷′ with 𝑦 ≤ 𝑥 and 𝑦𝑇 = 𝑥𝑇 . Note that flipping the i-th bit from 0 to 1 makes 𝑦 to 𝑦′, and also make 𝐷′ to 𝐶′ ⊆ 𝐵′. This implies that 𝑦𝑇 ′ = 𝑥𝑇 𝑖 where 𝑥 𝑖 is the string obtained from x by flipping the i-th bit. Note that 𝑥 𝑖 ∈ 𝐶 ′ ⊆ 𝐵′. Thus 𝑦 ′ is a lower k-limit for 𝐵′. □

After the second step of the proof of Theorem 2.we get a setB withand B does not have a lower k-limit in A.Thus by the above lemma,we know that |Bg≤k'. References [Tsa01]Shi-Chun Tsai,A depth 3 circuit lower bound for the parity function,Journal of Information Science and Engineering 17(5),857-860,2001. [HJP95]J.Hastad,S.Jukna,and P.Pudlak,Top-down lower bounds for depth-three circuits,Computational Complexity 5,99-112,1995

After the second step of the proof of Theorem 2.2, we get a set 𝐵𝑔 ′ with |𝐵𝑔 ′ | ≥ ( 𝑚 𝑟 ) /𝑙, and 𝐵𝑔 ′ does not have a lower k-limit in A. Thus by the above lemma, we know that ( 𝑚 𝑟 ) 𝑙 ≤ |𝐵𝑔 ′ | ≤ 𝑘 𝑟 . References [Tsa01] Shi-Chun Tsai, A depth 3 circuit lower bound for the parity function, Journal of Information Science and Engineering 17(5), 857–860, 2001. [HJP95] J. Hastad, S. Jukna, and P. Pudlak, Top-down lower bounds for depth-three circuits, Computational Complexity 5, 99–112, 1995