Lecture 55

Okay, so good morning everyone. So last time we saw how we can reduce the depth of a AC0 circuit using a threshold circuit and we can bring it down to depth 3. So there were two important points that we assumed, we did not prove. First is the kind of circuit that we constructed had one majority gate at the top followed by parity gates at the second level and then it had AND gates at the third level and the second is of course the Bailey and Vazirani theorem that gave us the fact that if you look at the sequence of sets Si, there will be some i which is of size 1, such that Si has size 1. So we will look at the proof of these two results. First, let me start by looking at the first point. So okay, so we will state the following results. So let E be a depth 2 circuit having a majority gate of N in R at the top and parity gates and 2M in second level, then C can be accepted by 2 threshold circuit having 2RM plus 1. So pictorially what we are saying is that suppose I have a majority gate followed by parity gates below it and this has fan in R and all these gates have fan in at most 2M, then I can reduce this to a circuit which will have one majority gate at the top and 2RM majority gates in level 2. This is what will show and this would kind of tell us that without any loss of generality, we can assume the circuit to have only majority gates. So just for the construction, just so that we, so we will be giving a construction, right? Just so that the construction is easier and it works, we assume it is 2M. So again, so if let us say the fan in is less than 2M, then we can add dummy gates to make it 2M. So we can add some 0s or 1s depending on what it is, M is any variable, so M and R are variables for us. So basically M and R determine what would be the size of this. So what is the construction? So we will argue that okay, suppose I have a parity gate, okay. So let G be a parity gate which has fan in 2M. So for this parity gate, I will build, I will replace this parity gate with 2M majority gates, okay. So replace with 2M majority gates and there are R of them. So therefore, I will get a total of 2RM gates at the second level. So what would be the construction? So what do we want? So we want to kind of simulate parity. So what does it mean to say simulate parity? It means that well, if the number of inputs is odd, then the parity gate should output 1 and if it is even, then it should output 0. So how do I simulate that using 2M majority gates? So what the idea here is that follows. So for each odd i between 1 and 2M, there are M many odd i's at majority gates, let me call them as, so this is for a gate G, so let me call them as HG1 and HG2 such that HG of 1 would accept its input if at least i inputs are 1 and HG2 accepts if at most i inputs are 1, okay. This is a majority gate that has the same input as this one, okay. So whatever is the input of this, let us call this some y, this will also be y and this also has the same y, okay. Now if at least i of the inputs of y are 1, then this guy accepts and if at most i of the inputs here are 1, then this guy accepts, okay. Now what does this mean? And I have 2M such gates, okay. So for each odd i, I have 2 gates. So therefore, I have a total of 2M gates. So what does this mean? Now if I look at this gate G, so if G accepts, which means that y has odd number of 1s, what does it tell us about these 2M gates now, how many of them will be 1? So there are an odd number of gates which are 1, okay. What does this tell us? For all j up to that particular i, okay, so let us say that y has i number of 1s, where i is odd. Yeah, so let us say y has an i, y has i number of 1s. So up to that i, these kind of gates will accept, right, because this has at most, this would accept at most of, I mean inputs are 1. And for all j that is greater than or equal to i, these gates would accept. How many gates are accepting in total? M plus 1, exactly, right. So exactly M plus 1 of the majority gates and if G rejects, which means y has even number of 1s, then for, let us say y has, again assume that y has i number of 1s. Now i is an even number, so i minus 1 is odd and i plus 1 is odd, okay. So till up to i minus 1, these gates would accept and from i plus 1, these gates would accept. So how many majority gates are accepting now? So exactly M of the majority gates. So now we have kind of broken this down into 2 things, so if G accepts, then exactly M plus 1 and if G rejects, then exactly M of these majority gates accept, okay. Now we have this, so this is the construction, so now we will have, as I said one majority gate at the top, so now I can finish it here, the top majority accepts if and only if at least how many of the second level majority gates should accept. So again just think about it, so I have a total of 2 RM gates now, okay. So I have, so for each G over here, I have a total of 2 M gates, right and anyway M gates are accepting, so it is between M and M plus 1, okay. So for R many parity gates, I anyway have RM many gates which are accepting, right. So it can be RM plus R or I mean it can be a maximum of RM plus 1 and it is a minimum of RM, right. So it is between RM and RM plus R, right. So when would this guy or when would this top majority gate accept? So here this guy would accept if greater than R of these guys are 1 or in other words greater than R by 2 are 1. So here when would this guy accept? RM plus R by 2, okay. So when greater than RM plus R by 2 of the majority gates in level 2 accept or output 1, okay. Because that means that at least I have or I have at least greater than R by 2 many ones from here because that would those R by 2 would contribute to a extra 1 over here and that is what I need. So this is the entire construction. So now this actually completes that entire proof. I mean assuming Valiant Vazirani, this completes the proof. So I have a depth 3 threshold circuit now, okay and of course below this if you look at the actual construction, so I have majority, I have parity followed by AND and we know that how AND can be converted to majority. So therefore I have a depth 3 threshold circuit which is accepting the same language, okay. So now let us come to the main part or the main technical part of the proof that is the result due to Valiant Vazirani. So let us call this as theorem. So what was the statement? So let S subset of 0, 1 to the power m be non-empty and W1 up to Wm are chosen at random. These are vectors which are chosen randomly and we define the first set to be our initial set and we construct these sequence of sets. So how do we construct this sequence? So basically each time we look at the space that is orthogonal to the current vector, okay and we keep on reducing the size of it that is Si is equal to all vectors in S such that V is orthogonal to W1, V is orthogonal to Wi. Then probability greater than one-fourth there exist an i such that Si is 1. This is what we used and this is what we are going to prove now. So yeah so this is the completely this is the proof that is completely based on linear algebra. So before getting into the proof just a few notations and facts we can observe a couple of facts. So first of all, okay so let Hw be the hyperplane of all vectors that are orthogonal to W. So we will use this notation, so this is also called the hyperplane corresponding to W and it is easy to see that this is actually a subspace as well, okay this is actually a well it is a vector space. We do not have a yeah if I look at the set of all vectors then this is a subspace of that space. Next what is the size of this subspace? How many vectors are there? So the total space 0, 1 to the power m, so F need not be a vector space, okay S is just some set. We cannot assume that S is a vector space but of course 0, 1 to the power m is a vector space over F2. So what is the size of this subspace? If W is not the all 0 vector exactly then this would be yeah so let us assume yeah so if W is not the all 0 vector then this is 2 to the power m minus 1. Now if I look at let us say intersection of this space, okay so let us say if I look at Hw1 up to Hwl what will be this? So I have this space now again I take another vector, okay and suppose they are all linearly independent. So one can show again using just simple linear algebra that this space, so every time actually I will take a vector which is linearly independent to the previous vectors the search space gets or this space gets cut in half, okay. So therefore this will be of size 2 to the power m minus l. Next we define span yeah this is our subspace of size 2 to the power m minus l, okay. Next I will define rank, so rank of S is the smallest number of vectors that span S, okay. So what is the smallest number of vectors inside S that would span the entire set, okay so that is called the rank of S. And the last point probably the most important point is that so what I want to work with so now so well again one can show that if I take the smallest number of vectors they will have to be linearly independent because if they are not then I can get a smaller size set. So I have this set of vectors which span the entire S and they are linearly independent as well but for us to work, okay so for us to prove this theorem what we need is a special set of such vectors, okay so namely the second yeah it is okay yeah. So what I need so for us to be able to prove this theorem what we need is not just any set of vectors but a special set of vectors namely the standard basis vectors, okay so that is basically the vectors which have a 1 at a single position and all 0s everywhere, okay. So one can show that so if S has rank k then by the W1 up to Wk then there exists a invertible m cross m matrix M such that ei equal to mWi where ei are the standard vectors in 0, 1 to the power m, okay. So again this is a standard idea that I can always do a change of base I mean this is not exactly a basis because S need not be a vector space but I can basically change from any linearly independent set to another set linearly independent anything that I want via a invertible matrix, okay and instead Wi and S we can now use MWi and so wherever we are dealing I mean wherever we have Wi I can replace that with MWi and wherever I have S I can replace that with M of S, okay. And everything else that we do for the rest of this proof, okay so basically dealing with probabilities making probability estimate talking about the size of sets inclusions and everything actually holds for if it holds for Wi it will hold for MWi if it holds for S it will hold for M of S and MWi is nothing but E of I. So I can without any loss of generality work with E of I, okay. Therefore without loss of generality we can assume that E1 up to EK spans S. So that is the background that we needed, okay. So now coming to the first I mean observation. So if W1 up to Wm-1 are chosen independently at random then we want to estimate what is the probability that these vectors are linearly independent. So suppose I take a set of some m-1 vectors what is the probability that they are linearly independent and we will show that this is greater than half. How does this proof work? So this is again just straightforward counting. So we will just count how many choices we have for each of these vectors. So first of all how many choice do I have for W1, what vector can W1 be, okay. So for this set to be linearly independent note that none of the vectors can be the all 0 vector, right. So for W1 I have 2 to the power m-1 many choices, okay. So 2 to the power m-1 choices. Now how many choices will I have for W2? So W2 cannot be anything that is in the span of W1, okay. How many vectors are there in the span of W1? Essentially there are 2 vectors, right. So W2 cannot be any of those 2 vectors, right. How many choices do I have for W3? Once again W3 cannot be any vector that is in the span of W1 and W2, okay. So these 2 vectors together will make span 4 vectors, okay. So it will be 2 to the power m-2 square, okay, these many choices. If I go down this way for m-1 I will have how many choices? For any i, I will have 2 to the power m-2 to the power i-1. So this will be m-m-2 choices, exactly, right. So now I will just estimate the probability that all these wi's and this is basically the number of choices so that they are linearly independent, so that they are linearly independent. It is exactly equal to the product of i going from 2 up to m, 2 to the power m-2 to the power m-i divided by 2 to the power m. So this is nothing but product of 1-1 over 2 to the power i, right. And this can be shown to be by induction one can show that this is greater than the sum of 1-the sum of 1-sigma 1 over 2 to the power i, i going from 2 up to. So this can be shown by induction. So what is this value? So for i going from 2 up to m, 1 over 2 to the power i, so basically this will be one-fourth plus one-eighth and so on. So this is greater than or equal to 1-half which is equal to, so this proves the lemma. Now I can also generalize this a little bit and make a slightly more general claim, okay. We call this as claim 4 that if w1 up to wm are chosen randomly from 0, 1 to the power m, then the probability that w1 up to wm are linearly independent will be how much? There will be another extra multiplication term. So the probability that these are linearly independent is the probability that w1 to w-1 is linearly independent first of all, which we have already estimated and wm does not lie in the span of those vectors. So what is the probability of that? That is 2 to the power m minus 2 to the power m minus 1 by 2 to the power m which is 1-half which is half, so half times half is one-fourth, okay. So this will be greater than 1. So this is just a corollary of the previous result directly. So we will use these two results.