noc21-cs49-lec36

So, we saw last time that sharp P can be simulated using an IP protocol and we were in the middle of showing how P space in particular the TQBF problem also has an IP protocol. So, I will just give a sketch of the argument I would not go into the details because the idea is basically the same I will just point out the extra work that the protocol needs to do and then we will look at something else. So, for the TQBF problem what the prover needs to convince the verifier is the following expression. Let us say that the last quantifier is a for all quantifier. So, we have a product of the polynomial is not 0. So, he wants to show that this whatever is the quantified Boolean formula psi that is given that is that belongs to TQBF in other words that evaluates to true. So, this polynomial should evaluate to non 0. So, this is what the aim of the prover is and. So, let us define. So, I did define this last time, but let us just recall. So, suppose we have a polynomial P. So, let P be a polynomial in N variables and define L x i of P to be equal to x i P x 1 through x i minus 1 1 x i plus 1 through x n plus 1 minus x i P x 1 through x minus 1 0 x i plus 1 up to x n. So, this is called the linearization operator on i. So, basically what this operator does as we saw last time with an example is that it just. So, any term any monomial in this polynomial P, where x i has a degree higher than 2 it just reduces that degree to 1 and the property that this operator has is that. So, suppose this operator is operated on a polynomial P in fact. So, if we operate the following operators on the polynomial P L x 1 L x 2 so on till L x n on P. So, this will give us some polynomial Q again in x 1 through x n with the nice property that Q is multilinear. In other words it is linear in each variable. So, it is a multivariate polynomial, but it is linear in each variable as opposed to P. And what we have is that if let us say each of these variables took their values from the set 0 1, then these 2 polynomials are identical. And identical is in the sense that for every setting of x 1 through x n they will give the same value ok. So, this is what we saw last time. And this basically follows from the trivial observation that if you take if you look at the equation x to the power k is equal to x, then for x belonging to 0 1 this equation is always true ok. So, this is basically the additional fact that we will use to show that the prover can convince the verifier that this is true. So, and if this is not true in other words if this is equal to 0, then with very low probability the prover will be able to convince this. So, what we will do is we will replace the following equation as follows. So, sigma x 1 pi x 2 pi x n of P phi is not equal to 0 if and only if sigma x 1 l x 1 pi x 2 l x 1 l x 2 so on till pi x n l x 1 l x 2 up to l x n of P phi is not equal to 0. So, basically what we do is that we intersperse these operators with the appropriate linear the linearization operators ok. And the idea behind is that whenever it is actually for some this is not required this is kind of redundant because we observe last time that summation does not increase the degree of the polynomial, but still I mean we will just keep it for the sake of completeness. But whenever I am applying this product operator what can happen due to this application is that the degree of the resultant polynomial might double up ok. But then when we apply these 2 operators successively what that makes what that will enable is it will bring down the degree of the resultant polynomial in x 1 and x 2 down to 1 and the same thing happens for all the other operators. So, now the protocol is again very similar. So, the protocol is the same as what we had for SAT bar or sharp P that is we will strip one operator at a time ok. So, what was the thing for sharp P? So, the prover sent a polynomial which was supposed to be equal to this entire thing ok. So, that is what the prover wants to convince the verifier, but the verifier is skeptical. So, what he does is he evaluates whatever the prover sends on 0 and 1 and if that is equal to whatever value the prover had started off with. So, in this case the prover will start off with 0. So, if that is the case then he evaluates that polynomial on some random point keep that the resultant value and send back the random variable back to the prover ok. Then in the next step the prover wants to convince that this polynomial or this expression is equal to a certain polynomial ok. So, one so you can think of these as an operator and in each iteration of the prover verifier interaction an operator gets stripped down. So, we know how to strip down in the case when the operator is a sigma operator or when it is a pi operator. So, suppose it is one of these linearization operators. So, what is the corresponding protocol? So, let Q a 1 to a k be equal to some L x 1 let us say I mean I can always rename my variable. So, that I is the first variable of let us say something like g a 1 through a k. So, then prover sends a polynomial let us say p hat we will check the following we checks. So, this is a polynomial in x 1. So, we checks if a 1 p hat of p hat of 1 p hat of 1 plus 1 minus a 1 p hat of 0 is equal to whatever is the prover trying to convince is equal to c where p wants to convince v that is equal to c yeah. So, if this check is satisfied by the prover then he will do the again the same thing. So, he will pick if true then v picks again it is the same thing he picks r randomly from the field f q computes the next c prime the c prime for the next round which is equal to p hat of r and then sends back r to the prover. And in the next round the aim of the prover is to convince is to send another polynomial such that it will strip the next operator and it will also convince the verifier that whatever is the correct expression I mean in the case that it is a linearization operator whatever is the p hat for the next iteration. So, p hat 1 plus 1 minus whatever is that operator a 1 p hat 0 should be equal to c prime and it proceeds in the same manner. So, again I mean there is nothing much different that is happening as far as the protocol is concerned it is the same thing, but the crucial fact was basically this observation. So, whenever x belongs to 0 1. So, this is basically the crucial fact. So, I would not go into the details of the error analysis you can read it from the book. So, any questions? So, the next thing that we will do is very different for in flavor from the kind of things that we have been seeing in the last few lectures. So, the next thing that we will do is what are known as circuit lower bounds and more specifically the result that we will show is that the parity problem does not belong to the circuit class A C 0. So, this is one of the first and one of the most important absolute lower bound results that is known in complexity. So, as I said many times it is very difficult to prove that something is not possible whether it is in complexity or in any theoretical computer science area because if I want to show that something is not possible I have to basically argue over all algorithms what I have to argue is that there is no algorithm in this universe which can do I mean of course, the algorithm will have some restricted amount of resources, but then it is not able to perform the task that we wanted to do. So, in this case what we are what we want to show is that suppose if we take a circuit which has constant depth polynomial size and unbounded fanon no matter what that circuit class it will never be able to compute the parity function. So, let us recall what the parity function is. So, the parity function I will just denote it with this symbol. So, the parity on n variables is just the sum of the individual bits modulo 2. So, if it sums up to an even number it is 0 otherwise it is 1. So, it is a very simple function and of course, I mean we know that there exist N C 1 circuit family I mean I mean there exist an N C 1 circuit which is able to compute parity quite easily, but when we come down to A C 0 this is not possible ok. So, there have been many proofs of this result. So, the first sort of proof was due to several people actually in different works and in. So, the first set of proofs were due to first sacks and sipser and subsequently it was improved by a hastad later on. So, this was in the early 80's and the way they came up with this proof was that in hastad's paper he showed a switching lemma. So, basically he showed that if I randomly restrict the variables of a function ok. So, suppose if I say that I have a function on x 1 to x n and let us say randomly restrict some of these variables that is I fix the values of some of the variables randomly. So, I get another function ok. So, that function will be I mean in non technical terms if I have a random restriction then we can show that. So, there will be a lot of difference between these 2 functions up to some I mean if you look at it from a certain point of view. So, I do not want to go into the details of that argument the reason why I mentioned this earlier result was because we will not look at this proof the proof that we will look at is one that was given by Rasborov and Smolenski in the late 80's and the idea of this proof is that. So, what they argue they argue in 2 parts in the first part they argue that if you have any AC 0 circuit ok. So, an AC 0 circuit can be approximated very well using a certain kind of a polynomial ok. So, whatever is the function that is being computed by an AC 0 circuit that can be approximated by a nice polynomial and in the second part they show that the parity function cannot be approximated up to any good approximation factor using such nice kind of polynomials ok. So, we will make these terms formal and together these 2 claims show that parity is not in AC 0. So, basically what we will show is that we will give a proof by contradiction. So, suppose if there is an AC 0 circuit for parity then we will get certain contradictions. So, let me write the main theorem that we are going to prove ok. So, for large enough N if C is a depth d circuit that computes parity on N variables, then size of C is at least one tenth of 2 to the power N to the power 1 over 2 d divided by 2. So, in other words if d is a constant ok. So, suppose d is 10 or something then we immediately see that the smallest size circuit that is able to compute parity must have size at least 2 to the power order N. For any constant d this is 2 to the power order N. So, an immediate corollary of this result is that this immediately implies that parity is not in AC 0. So, the main theorem that we will prove over today's and the next lecture is this theorem. So, the first thing that we will assume is that C has only NOT and OR gates ok. So, why can we assume this because using de Morgan's law we can replace any AND gate because suppose if we have an AND gate ok. So, this is the same as. So, by just introducing a 2 more levels I can replace any AND gate with an set of NOT and OR gates. So, we will look at the field F 3. So, let F 3 and we will just denote the elements in F 3 as minus 1 0 and 1 be the field of. So, as I said during our discussion of the IP protocol that fields have this nice property that they are closed under addition multiplication and they contain the inverses of these respective operations as well. So, I mean yeah. So, F 3 I mean by definition is the element 0 1 and 2, but here just we are using the symbol minus 1 to denote the element 2 because it is it makes things little more convenient for us. So, since we are denoting the element 2 as minus 1 just note of following properties that 1 plus 1 will be what? 1 plus 1 will be minus 1 and minus 1 plus minus 1 will be 1. So, the remaining equations are pretty much obvious. So, this is the only non obvious computation that is happening here yeah. So, the next idea is that a. So, P in F 3 x 1 through x n is a polynomial in n variables over the field F 3 ok. So, it takes its values from F 3 and the coefficients of the terms also lie in this field F 3. So, we say that P is a proper polynomial if for x 1 through x n belonging to 0 1, P of x 1 through x n also lies in 0 1 ok. So, suppose if we restrict the variables to take values only from 0 1 ok, since we are working in this field F 3 there is no guarantee that the value of the polynomial will also lie in 0 1, but if that happens then we will call such a polynomial to be a proper polynomial nothing much I mean just. So, one good thing about proper polynomial is that you can think of this as a Boolean function ok, you can think of this as a function which is. So, Boolean function is a function which takes values from 0 1 and it outputs a value in 0 1. So, proper polynomial although it is allowed to have values in the field F 3 it has this restriction that it is in 0 1. So, it has a nice connection to Boolean functions ok. So, the first lemma that we will show is that as I claimed earlier that if C is an AC 0 circuit then it can be approximated well using proper polynomials. In other words there exists a proper polynomial of degree at most ok. So, this is for all t. So, given an integer t greater than 0 there exists a proper polynomial of degree 2 t to the power d such that proper polynomial let us call it p such that p differs from C on at most size of C times 2 to the power n minus t inputs. So, totally since we are looking at n variate functions the total number of possible inputs can be 2 to the power n. So, what we are claiming here is that if you start with an AC 0 circuit then for any t greater than 0 there exists a proper polynomial having degree at most 2 t to the power d such that p will differ from the circuit on at most so many inputs ok. So, any questions so far? C is the same circuit that we started off with. So, what we want to show is that if there is a circuit C of depth d that computes parity then size of C is greater than this. So, this is what we want to show. So, we start off with a circuit C having depth d that computes parity on n variables and our goal is to show that size of C will be greater than this quantity. So, the first claim that we make is that for any t greater than 0 there is a proper polynomial that approximates t up to a very large factor ok. So, how do we do this? So, essentially this is a proof by an inductive construction. So, what we do is given C ok. So, let us say this is our circuit C and these are the input gates ok. So, we these are the input edges and finally, we have an output edge. So, what we will do is we will inductively associate a proper polynomial with each edge of my circuit ok. So, the polynomial that we will associate with the input edges is basically the polynomial x i ok. So, for x 1 we associate the monomial x 1 for x 2 we will give the monomial x 2 and for x n we will give the monomial x n. So, the first thing is that for input edges assign the monomial x i to variable x i and we will argue for each of our cases that it gives us a proper polynomial. So, clearly x i is a proper polynomial because if I mean it is the identity polynomial. So, if it is 0 or 1 we will just give back the same value. Secondly, suppose if we have a NOT gate and let p be the polynomial associated with the input of the NOT gate. So, what do we associate with the output of this NOT gate? So, we want to associate a polynomial that will somehow compute what the NOT gate does. So, we will associate 1 minus p. So, let us call it p prime. So, this is equal to 1 minus p and again yeah any ok. So, again clearly p prime is also a proper because if p is proper then 1 minus p again takes value in 0 and 1 and the second thing is that if the degree of the input is if degree of p is d then degree of 1 minus p is also d. The third case is the non-trivial case. So, suppose if we have an OR gate that has on its input edges the polynomials p 1 p 2 so on till let us say p k. So, we want to associate a polynomial to the output edge. So, what is the obvious polynomial to apply in this case? So, I want to write down a polynomial p prime such that p prime will evaluate to 1 if and only if at least one of these evaluate to 1. So, we can set that as 1 minus you can just do this going from i is equal to 1 to k and that will compute it correctly ok. But let us just analyze what will be the degree of this polynomial? What can be the degree of p prime? How large can it be? So, in general since it is an AC 0 circuit k can be as large as n ok. So, this degree therefore, can be as large as. So, suppose the maximum degree of the p i's where d ok. So, then this can be as large as how much? d to the power k or yeah I mean k can be as large as n. So, this can be as large as d to the power n ok. Sigma of p i. So, suppose you have only 3 gates that have 1 and the remaining gates are all 0. So, sigma of the p i's will be sum of those 3 gates that have 1 and since we are operating over f 3 that will output 0 1 plus 1 plus 1 is 3 and modulo 3 that is 0. So, summation will not work. I mean had summation or something or some other computation which had such low degree complexity indeed work then it would have been good for us, but this is kind of the smallest polynomial that is that will compute or yeah. So, the problem here is that. So, now, let us analyze what will be the output of or what will be the degree of the output polynomial. So, we have a depth d circuit and in each depth we can compute an or gate. So, we start with at the base level where we have all degree 1's. So, from degree 1 no this is not d to the power n this is d n right because with each product I am just adding a degree d to it yeah. So, what will be the suppose if I have a circuit C and if we apply this polynomial to an or gate what can be the potential degree of the polynomial at the output edge. We are multiplying it by n. So, we start with 1 and we have a depth that is equal to d. So, maybe d is not the correct thing to use. So, finally, what can it be? So, it is n times n times n times n. So, it is it can go up to n to the power d ok. So, this is quite large. So, this is clearly something that is not allowed because ultimately what we want is to have a polynomial that has degree at most 2 t to the power d for any t greater than 0 and n can be much larger than the t that we start off with. So, this thing does not work. So, what we do in the case of or gates is that suppose if we an or if we have an or gate which has inputs p 1 through p k. So, we will pick subsets s 1 up to s t. So, these are subsets of 1 through k uniformly at random ok. So, whatever that p that is given to us we will pick t subsets and they will be chosen uniformly at random that is for each subset we will independently decide whether to put on a particular index i or not ok. So, I mean we can just do a coin toss I mean for each k we will just do a coin toss if it comes out head we will put in that i and if it comes out tail we will not put in that i and this way we will construct our t subsets. And then we will define q j as equal to sigma i belonging to S j p i whole square for j in 1 to t ok. So, for each of those subsets I will sum up the corresponding p i's that I mean such that the indices of those p i are obtained from that subset and then take the square and now I will just apply this or function. So, now, I will define this p prime to be equal to 1 minus product of the j's. So, j going from 1 through t 1 minus q j. So, clearly what we see here is that now p prime is basically an or of these q j's. So, if any of these q j's evaluate to 1 then p prime will evaluate to 1 and if all of the q j's are equal to 0 then p prime will be 0 ok. And if you just analyze the degree if we have this polynomial as the output polynomial of an or gate and if let us say d is the maximum degree of our p i's then the degree of. So, what will be the output I mean the degree of the output polynomial. So, let us say the maximum degree of the p i's is d. So, what will be the degree of q j 2 d and what will be the degree of p prime 2 t d right. So, the maximum degree of p primes is 2 t d ok. So, now, if you have a depth d circuit. So, we start off at the base layer with monomial that is polynomials of degree 1. So, by the time we go to depth d the polynomials degree will not be more than 2 t to the power d ok. So, we will just stop here and we will complete the error analysis next time, but this is just one part of the proof in the next part we also have to show that parity cannot be approximated in this manner. So, here what we are saying is that a c 0 can be approximated by a proper polynomial we will show next that there is no proper polynomial that approximates parity in a well fashion.