Lecture 42

Anyway, so this is the structure that we require, now let us look at the 2 results that we will be proving, the 2 main results. So what we will show today is the following result, let me call it as lemma 1 for all D and for sufficiently large N, there is no depth D circuit computing parity having, but last size less than 2 to the power one-tenth N to the power 1 over D minus 1 and bottom fan-in less than or equal to one-tenth N to the power 1 over D minus 1. I actually erase the previous theorem, but note that if I can prove this lemma, then actually I get a proof of the previous theorem, how do I get a proof of the previous theorem? Suppose this lemma is true, now look at the previous theorem that I stated that any circuit of or for parity there is no depth D circuit having size smaller than 2 to the power one-tenth N to the power 1 over D. Now suppose the contrary, suppose there is a circuit computing parity which has size 2 to the power one-tenth N to the power 1 over D, what I will do is I will use that circuit, so I will take that circuit and I will just add a dummy bottom layer, so basically for all the literals at the bottom I will just shift them down by one step and I will just add a dummy layer of whatever AND or OR gates and whatever is not above it, okay. So basically a set of gates which have fan-in and fan-out exactly one, so it just takes its input and sends it up, okay, so it is not changing whatever that circuit is computing. Now what does that achieve? What that achieves is it makes the bottom fan-in first of all one, whatever was the earlier bottom fan-in that is changed to one, but the depth increases by one now, right. But now what that means is that I am getting a D plus one circuit, okay, which has bottom fan-in one and which has size bounded by 2 to the power one-tenth N to the power 1 over D now, so therefore it will be contradicting this lemma, okay, because now instead of D I have gone to D plus one, so it is contradicting this, okay. So if I am able to prove this lemma it is sufficient to prove the theorem. So how do we prove this lemma? So here is where Hastad's main result comes in, so to prove this lemma what he actually gave is what is popularly known as Hastad's switching lemma. So actually this is not just a lemma, I mean this is quite a complicated result and it is much more than just a lemma, but this is what it is popularly known as. So what this lemma says is that given a T, C and F, F apply a random restriction rho on it that leaves P and variables unfixed, P less than half, in fact we can take it to be strictly less than half, then the probability over this choice of random restriction that F cannot be represented as a T-DNF is at most gamma S over here, sorry, not T, I will use as an S-DNF is at most gamma P T whole to the power S where gamma is a constant, where gamma is equal to ln of 2 to the power, sorry, 2 by root 5, I think correctly. So this term is approximately equal to 4.16, it is less than 5, okay. So let us try to understand what this switching lemma is saying. So what the switching lemma is saying is that well if I have a function which is representable as a T-CNF, okay, so basically the function can be written as in a CNF form where each clause has at most T literals, okay, so it has a small representation, then with high probability, okay, it can be represented as a S-DNF or in other words the probability that it cannot be written as an S-DNF is small, okay, so as well, yeah, so as S increases the value of this decreases. So with high probability, it can be represented as an S-DNF as well. So in other words if a function, so another way of looking at it, if a function is restricted in some sense, so because it can be written as a T-CNF, it has a restricted form, then we can actually change the representation of that function into an S-DNF with high probability. And that is what this is saying and we will prove this lemma using, I mean, heavily using this switching lemma of Hasta, okay, so yeah, so this is all the setting and now what we will do for the rest of today's class is prove lemma 1 using lemma 2, so any questions? So let me give an idea of the proof, okay, so how does this proof proceed, so what is the intuition behind this proof? So what, the way we prove lemma 1 is first of all, of course, we assume that, suppose the lemma is not true, that is we will assume a circuit, a canonical circuit for parity that has size smaller than this quantity, okay, we will assume there is a depth D size, there is, yeah, so there is a depth D size circuit having size smaller than this and then what we will do is that, we will show that well, if I take the function that is computed by this bottom layer, okay, so let us say I take the function computed by this sub tree, okay, this is some function, now I will take a random restriction and I will show that I can actually flip this AND gate into an OR gate, okay, no, actually not this, so I have to take a DNF over here, so I will take actually this, the function computed by this sub tree and I will flip this from a, so here it is a DNF, I will flip it into a CNF and I will do this for each one of these sub circuits over here. Now, what do I get as a result? Now once this becomes a CNF, the top gate becomes an AND gate, now once the top gate becomes an AND gate for all these sub circuits, I can actually merge adjacent AND gates and get a circuit which has depth 1 less than the original depth and there are some calculations in between that will be used to show that well, this smaller depth circuit is still computing parity of a large number of inputs, okay. So, now actually our input is restricted, so because we are using random restriction, several variables are set to either 0 or 1 but still there are several variables which are unfixed, okay and that would depend on our choice of P, okay, what P we choose, so our P will actually be quite small, so in each level will be just fixing a small number of variables and we will show that still there are lot of free variables that are left, lot of unfixed variables that are left and this smaller depth circuit is still computing the parity of all those remaining variables because I mean, parity on this unrestricted variable, I mean sorry, so whatever unrestricted variables that I have, they are also computing parity on those unrestricted variables, okay because if I flip any one of those unrestricted variable, the value of the parity function changes and that would give us a contradiction, so this is roughly the intuition as to how the proof will proceed. So, now let us look at the details, okay, so any questions, S will be, so these are parameters, so S and T are parameters, okay, so we will fix them, so this is, this depends on us, so I take a TCNF, okay, so think of it anything, so think of T as maybe 3, okay, maybe you can also think of S as 3, so if I take a 3CNF, so suppose I have a function which is representable as a 3CNF, I can apply random restriction and then what the switching lemma says is that with probability, with high probability that is with probability 1 minus this, the restricted function, okay, actually this is slightly wrong, so this would be F restricted to row over here, so this restricted function can also be represented as a 3DNF with high probability. So as, so note that as S grows, this thing decreases, the probability decreases, these are less than 1, yeah, this would be less than 1, we will choose them to be less than 1, so that is that will depend on our choice, so gamma is of course fixed, P is of course less than 1, we will choose T such that well, T into gamma is well, this entire thing is less than 1, because otherwise probability does not make sense, okay, so these of course, yeah, so this is not true for any T and any S, this will only be true for those settings for which this is less than 1 and the way we will choose them, it would turn out to be less than 1, this value decreases, so which means that getting higher and that is what is expected, right, if you allow larger DNFs, if you allow DNFs with larger terms, then you should be able to represent F, that is what is expected, right, so intuitively that makes sense. If you restrict the DNFs to have very small, I mean very small literals per term, then the chance that it can be represented actually decreases, that is exactly what this is saying, okay, anything else? So, now let us just fix the details and complete the proof of Lemma 1, yeah, so as I said the proof will proceed by, yeah, so what we will show is that the proof proceeds by induction on D, now for D equal to 1 and 2, the proof is true trivially, so if D is equal to 1, then it is just, so if D is equal to 1, then it is just an AND or an OR gate, okay, in which case the proof is trivially true and if D is equal to 2, then, so what happens if D equals to 2, so if D is equal to 2, then what is the bottom fan-in that we have, so if D is equal to 2, then the bottom fan-in that we have is less than N, okay, so it is N to the power 1, so it is N by 10 basically, right and if I have a circuit whose bottom fan-in is less than N, then I know that it cannot compute parity, that is something that we already argued, so the Lemma is true for D equal to 1 and 2. Now let us assume Lemma is for some D minus 1, okay, greater than or equal to 2, okay, what does that mean? That means that for N greater than or equal to some large number capital N, there is no depth D minus 1 circuit having but last size less than or equal to 2 to the power 1 over 10, N to the power 1 over D minus 2 and bottom fan-in less than or equal to one-tenth of N to the power 1 over D minus 2, so there is no depth D minus 1 circuit computing parity or for parity, right. So, suppose this is true for all D up to D minus 1, now let us look at what happens for D, now for the sake of contradiction we will assume that the negation of this, okay that is there exist a circuit for size D, now for D assume the contrary that is yeah, so suppose the Lemma is not true for D, okay that is for arbitrarily large N, there exist a depth circuit for parity having but last size less than 2 to the power one-tenth of N to the power 1 over D minus 1 and bottom fan-in at most one-tenth of N to the power 1 over D minus 1, so for arbitrarily large N, suppose there is a circuit for parity, so now what can we say? So, now we will choose N, okay so because this is true for arbitrarily large N, I will choose N to have a particular form, okay, so choose my N such that it satisfies 2 constraint is still greater than this constant capital N that we had and do I need gamma by 5 raised to the power one-tenth N to the power 1 over D minus 1 is less than one-third, okay, now note that as so this exponent over here is less than 1, right, so I can choose N large enough so that even with this exponent, this left hand side term is greater than capital N, so there is some value of N for which this is true and here, so this gamma is less than 5, so this quantity is less than 1, so I can again choose N large enough, so that with this power, this term becomes less than one-third and take N to be the maximum of these 2, okay, so take N which satisfies both these 2 constraints, okay. So, because N is arbitrarily large, I can always choose such an N and let C be the associated circuit, so for that value of N and for depth D, let C be that particular circuit which has bottom fan in at most this and butt last size at most this, okay, now we will apply the switching lemma, okay, so now we will see how we can apply the switching lemma, so let H1, H2 dot dot dot, let T1, T2 be the bottom subtrees of C, okay, so we have this circuit C and by bottom subtree, I mean the subtree that we get by considering the last 2 layers and without loss of generality, assume that these subtrees are in CNF form and let H1, H2 be the corresponding functions computed by these subtrees, so without, so now this is important point here, I will just explain, so without loss of generality assume that H i's are T CNF's for T equal to this bottom fan in which is one-tenth N to the power 1 over D minus 1, okay. So, now the bottom fan in is bounded by this actually comes from our assumption, so that is not a problem, so I can choose T to be this quantity and I do get that the bottom fan is now bounded by T but why is this a CNF, why not a DNF, I mean why is it this, why is it that these functions are end of ORs, okay, so now that actually does not matter, so this switching lemma, this entire switching lemma that we have in this lemma, I can replace CNF with DNF and vice versa and still this lemma remains true, so whatever this lemma says is actually also true if I have a T DNF over here and I have a S CNF over here, okay, so this actually does not depend on the fact that this is specifically CNF and this is DNF, if I just interchange the rows even then the entire result remains the same, so that we will see when we look at the proof of the switching lemma. Now, here I am just assuming without loss of generality that at the bottom layers, if I look at these bottom subtrees, they are in CNF form, so if they are in DNF forms, I will just use the other form of the switching lemma, that is the reason why I can assume this without any loss of generality because I have written the switching lemma in this form that is why I am assuming it to be CNF but it does not matter but the point is that it is either a T CNF or a T DNF that is what is important, so we have these HI's which are T DNF, now we will apply the switching lemma over here, right. So, let I will choose my probability, so let P be N to the power minus 1 over D minus 1, so now note that for D greater than or equal to 3, this quantity I mean, this probability is clearly less than half, so this satisfies my condition that the probability is less than half and rho be a random P restriction, okay then by switching lemma, what we have is probability for all HI in fact, probability that HI restricted to rho, I will just write this a little differently is not a T DNF is at most gamma PT whole to the power T, so I choose my S to be T as well over here that is why I get gamma PT to the power T, right and this is true for each and every HI, okay. So, because all the HI's have bottom fan in that is bounded by one tenth N to the power 1 over D minus 1 which is my value of T, I can apply this, okay, so if I apply a random restriction rho, a random P restriction rho then with probability at most this, this will not be a T DNF or this is, so yeah, so what I mean by this sentence, so this sentence is a little bit different from the way I wrote it, so this actually means that HI cannot be represented as a T DNF, okay, I should not, it does not make sense to say that a function is not a T DNF, it is not representable as a T DNF, okay. So, any questions? From a TCNF, from a TCNF we are converting it into a T DNF, so the way we choose, so the reason why we choose those is because finally we want the probability calculation to be bounded by something, so our choice of, so here I have already chosen my parameters, I have already chosen T to be this quantity and I have chosen P to be this quantity, well, so you are, so what is your question? Why is it bounded by T or why is it a CNF, what is your question? Why? Because the bottom fan is bounded by this, so look at, no, so that is the inductive assumption that for all, up to all D minus 1 the lemma is true, okay, so now we are assuming that suppose it is not true for D which means there is a circuit, depth D circuit that is computing parity for arbitrarily large N whose size is bounded by this and whose bottom fan is bounded by this. Now, under this assumption we are going forward, now if the bottom fan is bounded by D then of course what we get is a TCNF and T DNF at the bottom, so all the, so we are looking at CNFs over here, so all the clauses that I get at the bottom will have at most T literals, therefore it is a TCNF. Now we are making that there exist a circuit, so the, what we want to prove is that there is no circuit of depth D which has this, now we are saying suppose there is a circuit, then we will get a contradiction to this, we will see how we get a contradiction, yeah, you can think of it as size also, so what we are assuming is that there is a circuit which has bounded size and bounded bottom fan N which is able to compute parity for arbitrarily large N.