Lecture 56

Now, let us come to the Weylian-Bazirani's theorem. So, let me state the next claim or maybe let me call this as a lemma, let us call this as lemma 5. So, okay, so before proving this lemma, we can actually prove one case of the theorem, which is easy to see. So, if 0 to the power m belongs to S, okay, suppose the all 0 vectors belong to the set W, then what can we say? So, if 0 to the power m belongs to S, I know that with probability, so if I choose m vectors with probability at least one-fourth, I know that they are all linearly independent. If they are all linearly independent, what can I say about this space are linearly independent? If they are linearly independent, what can I say about the size of the space? So, by just applying this, what do I get? Exactly, it is 1 and the subspace which has size 1 is the basically the only 0 subspace, right? So, this contains this has size 1. So, yeah, this is basically the space which has the all 0 vectors and now because S belongs to sorry, because 0 to the power m belongs to S. So, therefore, S of m which is nothing but S intersection with all these sets is equal to 1. This is the easy case. Now, we assume that 0 to the power m does not belong to, okay. So, our next lemma will be under that assumption. So, if let 0 to the power m be not in S, S has rank some k and w be a vector that is chosen randomly from 0, 1 to the power, then the probability that S intersection hw is not empty given that S is not a subset of hw is at least 2 to the power k – 2 divided by 2 to the power k – 1, okay. So, we want to find out that well, if I take so, essentially what I am trying to estimate here is that I want to yeah, so, I want to look at the sequence right, I want to look at the sequence from S 0 to S 1 to S 3 and so on. So, at any point in time what I am looking what I am doing is that I am looking at the previous S and I am doing an intersection with the space hw for the next w, right. So, I want to estimate the probability that when I do that intersection, what is the probability that that set will still remain nonzero, okay. That is when I do a when I take w1 and I do S intersection w1 it remains nonzero then I will set that to be my new S and I do that intersection hw2 that will also remain nonzero given the fact that S is a subset of this. So, I want to estimate this probability over here. How do we do this? So, we will do this by again counting. So, let us look at a equivalent condition. So, S not a subset of hw, what does that mean? So, S not being a subset of hw, so, what does it mean to say S is a subset of hw? It means that all the e1 up to ei's belong to hw. So, S not a subset of hw means that there is some ei, there exist i such that ei is not in hw, correct? Because if all the ei's belong to hw, then S will also belong to hw because S is spanned by these ei's. So, there is some i which does not belong to hw. If there is some i which does not and this is if and only if, right? The other direction is very obvious that if an ei does not belong to hw, then of course, S, the direction, yeah, of course, if there exist an i such that ei does not belong to hw, then S does not belong to hw that is very clear, I mean, at least one vector does not lie over there. Now, what does this mean? This means that what would be the form of w. So, what does it mean to say that ei does not belong to hw? So, hw is all those vectors which are orthogonal to w, ei does not belong to hw means that ei is not orthogonal to w, which means that ei dot w is equal to 1. So, let me write this ei dot w has to be 1, there exist an i such that ei dot w is equal to 1. If ei dot w is equal to 1, what does that tell us about w? w must have because ei has only 1 1 at the ith position everything else is 0, it means that w must have a 1 at the ith position. So, exist a position i in w, which is 1. So, therefore, I can say another way to say this is that w is not of the form 0 to the power k 0 1 to the power m minus k. So, that remaining the last m minus k positions can be anything I do not care, but in the first k position, w cannot have all zeros, there has to be a 1 somewhere that is exactly what this is and how many such vectors are there, which satisfies this condition exactly. So, there are total of 2 to the power m possibilities total of 2 to the power m, w is not of this form. So, this form means that there are 2 to the power m minus k vectors. So, w has a choice of being any of those 2 to the power m minus 2 to the power m minus k vectors. Now, so, this is so, we have given a combinatorial interpretation of this condition. So, now, let us look at the combinatorial interpretation of this condition, because we want to estimate probability. So, therefore, it is easier if we can get a combinatorial interpretation. So, S intersection Hw non-empty, what does that mean? So, it means that well, there exist i such that ei must belong to Hw, because if all the ei's does not belong to Hw, then S intersection H will be empty. So, there has to be some i which will belong to Hw. Now, what does that mean? If ei belongs to Hw, then by this same result, what we have is that ei dot w is equal to 0 and ei dot w equal to 0. What does that mean? It means that at the ith position, w must have a 0. So, therefore, it cannot be that w is of the form 1 to the power k 0 1 to the power m minus k, because if w is of the form it has all 1s in the first k position, then no matter which standard vector you multiply it with, it will always be 1 and that cannot happen. Because if that happens, then for all i, ei will not be in Hw. If for all i, ei is not in Hw, then S intersection Hw is empty. So, therefore, for these two conditions, I have that it is not of these two. Now, we come to the probability estimate. So, the probability that S intersection Hw is non-empty given S is not a subset of Hw is at least probability A given B is probability of A intersection B divided by probability of B. The probability of A intersection B is that both these two events happen that is w is not of this form as well as w is not of this form. So, therefore, from these two m choices, I am ruling out 2 times 2 to the power m minus k at least these many. There can be some commonalities which can actually reduce this, but at least there has to be this many vectors which are not of this form and not of this form. And the denominator is fixed, that is probability of B which is 2 to the power m minus 2 to the power m minus k. So, actually, I mean the correct way to look at it is that both the numerator and denominator is basically this divided by 2 to the power m and this divided by 2 to the power m, but that cancels out. So, I get this. And now, if you just simplify this, you will get 2 to the power k minus 2 and 2 to the power k minus 1 as we want. So, essentially, what is the idea here? The idea is we are kind of counting how many bad vectors are there for each of these two cases. And we see that there are the same number of bad vectors and therefore, this works for us. So, now, the last lemma we need, we call it lemma 6. So, let 0 to the power m be not in S and w1, w2 be chosen independently random and also let S0 be S and S i be S intersection with hw1 up to hwi. Then with probability, the probability that there exists an i in N such that S of i is 1 is at least. So, this lemma actually looks very close to the Valiant-Vazirani theorem, but the difference I will tell you what the difference. Of course, the first is we are assuming 0 to the power m does not belong to S because the other case is taken care of. The other important point here is that here we are not putting a bound on this, we do not have a bound on this sequence. If you look at Valiant-Vazirani, it says that there exists. So, in a set of m vectors, there exists an i less than or equal to m such that this condition happens. Here we are saying that there will be some i for which this happens. We want to just estimate this and then once we have proved this, we will show that actually we can work with i at most m minus 1 only. We do not even have to go to m, m minus 1 would suffice. Make sure I have it correct. Yeah, of course, I did not say here that S is a subset of 0, 1 to the power m that is anyway the assumption. And another difference is that we are actually proving something a little more stronger. So, instead of one-fourth, we are actually showing it to be greater than half over here. So, it is a slightly better result. So, how does the proof go? So, the proof will be by induction on the rank of S. So, let rank of S be equal to some k. So, the proof is by induction on k and what we will show is, so our inductive hypothesis will be the following. So, our inductive hypothesis is that probability there exists i in N such that S of i is equal to 1 is greater than or equal to 2 to the power k minus 1 divided by 2 to the power k minus 1. Now, if you actually take any value, so if you take any value of k that is greater than or equal to 1, you can actually work this out that this would be how much? This will be greater than half for all k greater than or equal to 1 because if you take k equal to 1, then this is exactly half and as k keeps on increasing, this quantity actually keeps on going towards 1. So, for k infinity, I think this limit tends to 1 as k goes to infinity, it starts off at 1 is it. So, here I have 2 to the power 0 which is 1 divided by 2 minus 1 is 1. So, yeah, so it starts off at 1 and then the limit goes to half, correct. So, the limit, yeah, okay. So, this is what we prove. So, now the base case, so in fact, we can say the following that if first of all k equal to 0 is not possible. So, what does it mean to say k equal to 0, rank of S is 0, rank of S is 0 means that S has only the all 0s vector, but our assumption is that all 0 vector is not in S, okay, it is not possible since 0 to the power n is not in S. Now, if k equal to 1, then rank of S is equal to 1, rank of S is equal to 1 means that S has only 1 vector. So, therefore, S 0 which is S itself is size 1. Now, the induction step, okay, so we assume it to be true for k minus 1 and we will show it to be true for k. First of all, following claim that with probability equal to 1, there exists i such that rank of S of i is strictly less than k and rank of S of i minus 1 is equal to k, okay. So, essentially what we are saying is that if I take this sequence, okay, now initially, of course, rank of S 0 is k. Now, it can happen that after I take S intersection H w1, the rank stays k. So, at some point, I am bound to meet with a wi such that its rank decreases. Now, why is that? Why should this happen with probability 1? So, again, the reason is that the probability that when I choose a vector, it does not decrease its rank is some probability that is less than 1, okay. So, if I choose a vector, and the rank does not decrease, the probability of that happening is some value that is less than 1. Now, I have this product operator. So, what is the probability that none of the vectors in this sequence reduces the rank, okay. So, it is basically that probability times itself times itself, and so on. So, now, let us say that probability was p, it is actually basically p times p times p, it keeps on going, right. And this is a geometric series that actually tends to 0. Okay, this is a geometric, in fact, a sequence not a series, this is a geometric sequence that tends to 0. Okay, so, if I look at the ith w, the probability that none of the wi's none of the wj's up to wi decreases the rank is some 1 over p to the power i. So, it never happens the probability of that happening is 0. Therefore, with probability 1, the complement event is that there is some i which will reduce the rank at some point. So, let i be the first such i that is till s minus 1 it did not reduce and at si it is reducing. Okay, so, this is I mean, this argument is again similar to saying that if I do a sequence of coin tosses, okay, what is the probability that I will get some head that is always 1. Okay, because the probability that I keep on getting tails is a geometric sequence that tends to 0, same idea. No, there is no bound here. Yes, it can go. But then we will show that yeah, so, then what we will show after this is that well, the probability that so, here actually wi's can be anything, but then we will show that if they are actually linearly independent, then there is a bound. And then we will use this result that the probability that they are linearly independent is something. So, now multiplying these 2, I get a bound as well as I get a I mean, I get a bound by this and I get a value of the probability by this argument. That is the last part. Yeah, so, I will be using this but anyway we can. So, if rank of s i minus 1 is less than k, what does that mean? So, if rank of s i minus 1 is sorry, if rank of s i minus 1 is equal to k and rank of s i is less than k, it means that s i is yeah, s i minus 1 is not a subset of Hwi, right? Because if assume the converse, suppose if s i minus 1 were to be a subset of this, then s i which is actually equal to s i minus 1 intersection with Hwi will be equal to s i minus 1 right and the rank of s i minus 1 is k which means that the rank of s i will also be equal to k, but that contradicts our assumption. Therefore, s i minus 1 has to be a subset. So, now we have that s i minus 1 is a subset of this. So, now I yeah, so, now we can apply lemma 5. So, by lemma 5, what do we have that the probability that so, now what is my s, my s is s of i minus 1, s of i minus 1 intersection Hwi is not empty, given that s is a subset s i minus 1 is a subset of Hwi, but that anyway we get okay. So, this thing is anyway happening for us. So, the probability of this happening is greater than 2 to the power k minus 2 divided by 2 to the power k minus 1 and what is this quantity. So, this quantity is nothing but s of by definition. So, now we can apply the induction hypothesis because now where have we come to, we have come to a set which has rank now less than k, s i has rank less than k. So, now we can apply the induction hypothesis by induction hypothesis probability that there exists we call it j belonging to N such that s of i intersection with Hwi plus 1 intersection up to Hwj is equal to 1 given that s of i is not empty is greater than or equal to. So, f i had rank less than k. So, therefore, this will be greater than or equal to where is our induction step 2 to the power k minus 2 divided by 2 to the power k minus 1 minus 1. And now if I combine these two, I get that probability there exists i in N such that s of i has size 1 is at most the product of these two 2 to the power k minus 2 divided by 2 to the power k minus 1 times 2 to the power k minus 2 divided by 2 to the power k minus 1 and this exactly turns out to be 2 to the power k minus 1 divided by 2 to the power k minus 1. So, here I can take a 2 common outside. So, these two will cancel out and here I get 2 to the power k minus 1 and divided by this. So, this proves the lemma 6 for us. So, now we come to the final conclusion of Vailley and Vazirani theorem. So, now with probability greater than half w 1 up to w m minus 1 are linearly independent. So, if I choose the set of some m minus 1 vectors with probability greater than half, they are linearly independent, we have already seen this. Now, what can I say about the size of this set? So, first of all, what can I say about the size of this part only? This will have size how much? So, 2 to the power m minus m minus 1 which is 2 and now I intersect that with s. So, what is the size of this at most? Now, we know that s does not contain. So, this way I mean this has size 2, but one of those vectors is the all 0 vector because this is a subspace and we know that s does not contain the all 0 vector. So, therefore, this set cannot be of size more than 1. Lemma 6 probability there exists i less than or equal to m minus 1 such that s of i is equal to 1 given that w 1 up to w m minus 1 are linearly independent is greater than half that is what we showed that if I have this given that they are linearly independent, the probability of this happening is greater than half. So, now, I just multiply the 2. So, therefore, the probability that there exists i less than m minus 1 such that s of i is equal to 1 is at most. So, of course, there are many ways. So, if I choose a sequence such that it is linearly independent the probability that I get this to be less than I mean I get an s i that is equal to 1 is greater than or equal to half and the probability that they are indeed linearly independent is another half the probability of both those events happening is at least 1 4 and this completes the proof of Valiant Vazirani. So, that is all. So, any questions? So, have you seen Valiant Vazirani earlier in complexity? So, you must have seen I had done this. So, basically it is used to show that well it gives a random reduction from sat to u sat and the idea is that. So, there the set of. So, there the set s is basically the set of solutions. So, from a set of solutions from a set of arbitrary number of solutions for sat you do this set of you do this keep on doing this dot product and you arrive at a set which has a unique solution. So, that is how it works over there and here also the idea is that from a set of what do I say. So, well f is a any arbitrary set of vectors for us. So, for our case it is basically those indices that we had that we considered last time the number of indices for which I mean the number of indices which are 1 in an OR gate how can I get to another I mean how can I convert it to a case where I have only 1 index which is going to 1. I keep on doing this dot product and I arrive at that.