What's the meaning of such a graph?It can be viewed as a"program"(therefore the name"branching program")that computes a function f as follows.On an input x=x1...xn,the program starts at the source node.If the node is labeled by xi,then the program reads xi,and depending on whether x;=0 and xi=1,follows the corresponding edge.The program continues this way until it reaches to one of the two sinks.then outputs 0 or I according to the label of the sink. The length ofa branching program is the number ofedges in a longest path.If the nodes can be arranged into a sequence oflevels with edges going only from one level to the next,then the width is the number of nodes of the largest level.(One can always add dummy nodes to make this happen without increasing the number of edges much.)Width corresponds to space,and length corresponds to time.If all nodes in the same level are labeled by the same variable,then the program is called oblivious.Our algorithm for the Parity function means that it can be computed by a width-2,length-n branching program. So branching programs are like decision tree algorithms(i.e.query algorithms)that we learned in the previous lecture.The difference is that if we have a bound for the width ofa branching program,then we essentially consider decision tree algorithms with the space limit. Now one natural question is:What's the computational power of branching programs of constant width and polynomial length?(For a concrete example,can it compute Majority?) Intuitively,this kind of program doesn't look powerful since the constant width is a bottleneck of how much information can be carried in the process of computation.Most researchers had indeed conjectured that it cannot compute functions such as Majority.Thus the following theorem by Barrington came as a big surprise. Theorem 1.2.Ifa Boolean function f can be computed by polynomial-size (AND,OR)formula on xi's and their negations,then it can also be computed by a branching program ofpolynomial length and width 5.(What's more,the program is oblivious. We can actually prove something stronger:If fcan be computed by a (AND,OR)circuit of depth d, then it can be computed by an oblivious branching program of width 5 and length 4d.(Then for formulaofsize s,its depth is at most d=log(s),so the branching program is of length at most 4d= s2) We want to simulate the circuit.By de Morgan rule,it's enough to simulate the negation and the (binary)AND gate.(It doesn't change the size ofa circuit much by stretching out an AND gate withWhat’s the meaning of such a graph? It can be viewed as a “program” (therefore the name “branching program”) that computes a function f as follows. On an input x = x1…xn, the program starts at the source node. If the node is labeled by xi , then the program reads xi , and depending on whether xi = 0 and xi = 1, follows the corresponding edge. The program continues this way until it reaches to one of the two sinks, then outputs 0 or 1 according to the label of the sink. The length of a branching program is the number of edges in a longest path.If the nodes can be arranged into a sequence of levels with edges going only from one level to the next, then the width is the number of nodes of the largest level.(One can always add dummy nodes to make this happen without increasing the number of edges much.) Width corresponds to space, and length corresponds to time. If all nodes in the same level are labeled by the same variable, then the program is called oblivious. Our algorithm for the Parity function means that it can be computed by a width-2, length-n branching program. So branching programs are like decision tree algorithms (i.e. query algorithms) that we learned in the previous lecture. The difference is that if we have a bound for the width of a branching program, then we essentially consider decision tree algorithms with the space limit. Now one natural question is: What’s the computational power of branching programs of constant width and polynomial length? (For a concrete example, can it compute Majority?) Intuitively, this kind of program doesn’t look powerful since the constant width is a bottleneck of how much information can be carried in the process of computation. Most researchers had indeed conjectured that it cannot compute functions such as Majority. Thus the following theorem by Barrington came as a big surprise. Theorem 1.2. If a Boolean function f can be computed by polynomial-size {AND,OR} formula on xi’s and their negations, then it can also be computed by a branching program of polynomial length and width 5. (What’s more, the program is oblivious.) We can actually prove something stronger: If f can be computed by a {AND,OR} circuit of depth d, then it can be computed by an oblivious branching program of width 5 and length 4d . (Then for formula of size s, its depth is at most d = log2(s), so the branching program is of length at most 4d = s 2 .) We want to simulate the circuit. By de Morgan rule, it’s enough to simulate the negation and the (binary) AND gate. (It doesn’t change the size of a circuit much by stretching out an AND gate with