With these two properties,we can prove the theorem by induction on d.Note that by de Morgan's rule, one can assume that the top gate is AND.So using the second property,the size blow up by a factor of 4 Finally,to use such a t-pemmutation branching program to compute f,one can just let the source be any ion the first level with t(i)i.Since te,such imust exist.Let the node t(i)on the last level by the 1-sink,and all other nodes links to a 0-sink. Finally let's come back to the original question of Majority function.It remains to show that Majority can be computed by a formula of polynomial size.This is indeed true;actually Valiant showed in [Val84]that it can be computed by a monotone formula of size O(n3.3). 2.From perfect matching to PIT and Circuit complexity 2.1 Bipartite perfect matching. Consider the following problem.Given an(n,n)-bipartite graph,decide whether it has a perfect matching.(Recall that a perfect matching is a permutation t s.t.every (i,(i))is an edge.) From the algorithm course,we know that the problem can be solved by transforming it into a max-flow problem.Here we present another algorithm which is more efficient for parallel computing. We associate an n-by-n matrix MG to the input graph G.The (i j)-entry of the matrix is xii if(i,j)EE, and 0 otherwise.By the definition of determinant,we have the following observation. Observation.Det(MG)is a zero polynomial if and only if G has a perfect matching. So to decide whether G has a perfect matching,it's sufficient to decide whether Det(MG)is a zero polynomial.Though this doesn't seem to be an easy job either,there is a very simple polynomial-time randomized algorithm based on the following famous lemma. Schwartz-Zippel Lemma.For any nonzero polynomial p(x1,...,x)over field F,if we pick n random elements ai,.,an from a subset S of F,Pr[p(a,.,an)=0]sdeg(p)/Sl. The lemma can be easily proven by induction on the deg(p);for an explicit proof,see the wiki page. In our bipartite matching problem,note that Det(MG)is a polynomial of variablesxi,and its degree is at most n.So we can just pick any field F ofsize,say,about n2,and pick random elements a,an from it.(Recall that for any N,there is a prime number p in [N,2N).So we can just pick F=Zp with p in [n2,2n2).Then let S=F.)Evaluate Det(MG)on(a1,..,an)to see whether it's 0.(Recall the fact thatWith these two properties, we can prove the theorem by induction on d. Note that by de Morgan’s rule, one can assume that the top gate is AND. So using the second property, the size blow up by a factor of 4. Finally, to use such a τ-permutation branching program to compute f, one can just let the source be any i on the first level with τ(i) ≠ i. Since τ ≠ e, such i must exist. Let the node τ(i) on the last level by the 1-sink, and all other nodes links to a 0-sink. Finally let’s come back to the original question of Majority function. It remains to show that Majority can be computed by a formula of polynomial size. This is indeed true; actually Valiant showed in [Val84] that it can be computed by a monotone formula of size O(n5.3). 2. From perfect matching to PIT and Circuit complexity 2.1 Bipartite perfect matching. Consider the following problem. Given an (n,n)-bipartite graph, decide whether it has a perfect matching. (Recall that a perfect matching is a permutation τ s.t. every (i, τ(i)) is an edge.) From the algorithm course, we know that the problem can be solved by transforming it into a max-flow problem. Here we present another algorithm which is more efficient for parallel computing. We associate an n-by-n matrix MG to the input graph G. The (i,j)-entry of the matrix is xij if (i,j)∈E, and 0 otherwise. By the definition of determinant, we have the following observation. Observation. Det(MG) is a zero polynomial if and only if G has a perfect matching. So to decide whether G has a perfect matching, it’s sufficient to decide whether Det(MG) is a zero polynomial. Though this doesn’t seem to be an easy job either, there is a very simple polynomial-time randomized algorithm based on the following famous lemma. Schwartz-Zippel Lemma. For any nonzero polynomial p(x1, …, xn) over field F, if we pick n random elements a1, .., an from a subset S of F, Pr[p(a1, .., an) = 0] ≤ deg(p)/|S|. The lemma can be easily proven by induction on the deg(p); for an explicit proof, see the wiki page. In our bipartite matching problem, note that Det(MG) is a polynomial of variables xij, and its degree is at most n. So we can just pick any field F of size, say, about n 2 , and pick random elements a1, .., an from it. (Recall that for any N, there is a prime number p in [N,2N). So we can just pick F = Zp with p in [n2 , 2n2 ). Then let S = F.) Evaluate Det(MG) on (a1, .., an) to see whether it’s 0. (Recall the fact that