Video 8-5: Derandomization

0:02 In the next section, we'll look at uh the implications of having such a pseudo random generator um before worrying about whether or not we have one or how likely it is that these exist. Um and then we'll we'll look at some constructions.

0:21 the specific constructions um we'll we'll look at look at in the next section is is from Nisan and Victoren and it's taking exactly what we hypothesized in the previous section namely that there is some some boolean function that has exponential hard on hardness on average uh and we'll show that this indeed implies a very strong pseudo random generator of essentially uh an exponential number of of of bits. So the formal statement we'll show is this under the assumption of this hypothesis and we can actually weaken it a little bit. The hypothesis that f is in np but it's good enough if you can just deterministically compute it in some exponential time. Uh that's it's it's a weaker requirement but good enough for the construction. And we need the this average on this a hard on average uh the average hardness um to be exponential expressed as some some constant delta here. Uh and then there's some construction that turns this into a pseudo random generator that also has an exponential um blow up in terms of how many bits does it generate from L input bits and the epsilon depends on this delta.

1:47 So what can we do with that? Why would we care? The thing is that it implies that BPP is exactly the same as P which means we can completely dandrandomize all possible polinomial time randomized algorithms at least of this Monte Carlo uh type. But remember BPP was already the most liberal version of that that made any sense. it was the two-sided version as opposed to any of the one-sided ones and it allowed uh bounded errors. But if you weaken that a tiny bit, you already get this PP class that seems uh way too uh generous. So in a way, this is the maximal statement you could expect. Randomization of any kind might not help at all for solving uh polomial time problems. It doesn't look like there's anything you gain by allowing randomness for the class of languages you can decide in polomial time.

2:51 So let's prove this. Uh first of all we use the previous theorem the existence of this uh strong pseudo random generator. We'll prove in the next section and hypothesis uh the hypothesis about the hard on average functions that we have a pseudo random generator with uh s of l bits out of any l seed bits and that that's an exponential function. That's the first step. Then let's uh pick an arbitrary language in BPP. That means there is some algorithm a which uh runs in polomial time definition of bpp and averaging over the randomness that we give the algorithm it computes the correct result with probability 2/3 right here L of X I'm just using this for the uh characteristic function of the language L and remember our probabilistic so algorithm A here is a it's a probabilistic Turing machine. So it always has these two tapes that we give it as input. Um one with the the actual word that we're checking whether it's in the language or not and one with the random bits.

4:25 Okay. uh and here in this statement r is truly random bits and let's use m for the number of random bits that this algorithm a is using and all we really need is that the number of random bits is at most the running time of the algorithm which is at most some polomial okay now we apply the d-randomization trick from before so out of this uh probabilistic touring machine. We construct a deterministic Turing machine where we um run a but on pseudo random bits generated with our pseudo random generator. So we have some uh some seed bits set but these are only L and then we generate an exponential's largest string G of set using our generator. And if you work out what the parameters have to be, we want that m is uh we want that m is is at le is is covered by s of l. We want the generator to produce enough pseudo random bits to run our our algorithm. And uh so you pick your l such that this is n to the c. And then what you have to do for that is pick a logarithmic number of bits and essentially the rest we've already somewhat checked that then the algorithm runs in polomial in polomial time because the C divided epsilon is just some constant.

5:59 So we'll simulate this uh instead of actually using a random seed we just go over all possible seeds generate the long string of random bits and then um run a on all those and do a majority vote. So same same idea as for uh slides few slides back for d- randomizing algorithms directly but what we dandomize is the seed of the pseudo random generator not the entire random bitst string if you check uh even even though the the pseudo random generator had this statement that it runs in exponential time that was exponential in L and that's logarithmic so again that's polinomial time uh and step two only does n to the c different uh seeds. So the whole thing uh runs in polomial time which means the algorithm that we get from there is is a p algorithm. Uh what we still have to check is that it actually computes the right uh function that it accepts the right strings.

7:13 And the intuition that you should keep here in mind is uh what we change from the standard from the the trivial dandomization is just that we now use pseudo random bits instead of going over all possible random bits. And so the intuition should be this is okay because uh our algorithm A is relatively efficient and so it shouldn't be able to distinguish between these pseudo random bits and the truly random bits that we previously defined it with. Um more formally what we'll do is is a proof by contradiction. So um we assume that it would not correctly compute the uh language um of X. So there must be some input or actually an infinite sequence of inputs. If there's only finitely many you could patch it. So there must be an infinite sequence of axis of increasing sizes. Then where uh the algorithm where B produces the wrong result which means the majority vote must have failed which in turn means that if I look at my original A and I use the pseudo random bits. I um have less than 1/2 uh of um so really B which really means that this this probability here must have been less than 1/2. But of course 1/2 is also less than the stated number there.

9:15 uh and that turns out to be um the original guarantee of a and then the slack that we allow as a difference between what algorithm is uh is doing on the real bits and on the pseudo random bits.

9:33 So uh if if B wasn't correct on on input X then we would have this uh we would have a different behavior for A on the pseudo random bits than on the real random bits and that intuitively means we can distinguish the the two the random bits and the pseudo random bits. So we have to construct um a circuit to do that because again pseudo random was defined um I think it would be lovely to have the definition here again um maybe just in case the whole thing uh I don't think we need all of it but don't want to run back another time.

10:26 I'll just put that here uh for now. It'll go away when we flip pages. But okay. Uh so the thing is that we have to show to um to arrive at a contradiction is that somehow we can build a distinguisher. So we have to find a circuit C that's small enough where the difference in behavior is is uh bigger than this 1 / 10. That's what we pick for epsilon.

10:58 Okay. Now intuitively C is easy. It just computes these these things. It computes uh a on x and random bits. And uh then the random bits that we put in indeed showed that if you put the pseudo random bits in, something different came out than uh when you put the real random bits in. But we also have this input x. And uh at this point um we're using that we're working with circuits as opposed to Turing machines because what's really convenient for circuits is that if you have uh some some algorithm a you can uh again we'll convert that to a circuit in the next step. Uh and it it has two inputs X and R. Then uh you can you can just imagine the variables being set to a specific value and then you just fold it in and so you can uh you can shrink the circuit to what's still variable. So you can hardwire specific inputs to have a specific value and that's a bit harder to do on touring machines. I guess you could still kind of try to simulate what the program does if certain positions in the input tape always have the same u same value but it's much harder to reason about. So this is the key step where we use the properties of circuits as opposed to some other model of computation.

12:31 So uh we don't have a circuit for a we have a touring machine but we can convert that. That's the theorem we've had in the previous section. uh you can build a circuit that has a size the square of the running time of the Turing machine you put in. And then here that works out to uh order n to the 2c.

12:58 And if you make n sufficiently large which which really means here the infinite sequence u for the contradiction you need that you can you can have a a violation for b for as large inputs as you want. So for a sufficiently long axis where B produces the wrong output, this um circuit C that we built N to the 2C with some constant will be smaller than N to the 3C which is this uh this threshold from the pseudo random generator. That's where again I still have it uh so we could paste it another time. So here we're using this part of the definition.

13:45 So you have to compare your circuit the distinguisher to this size threshold. And because for large enough n it's smaller than the threshold, it means it's a it's a valid counter example. The circuit we constructed shows that the pseudo random generator is broken. But we assumed that it is a correct pseudo random generator. So we arrive at a contradiction. Okay.

14:12 So that means the assumption was wrong and the majority votes is always correct. Maybe up to a finite number of inputs. Uh but this this you can patch separately. you can always make make a separate algorithm that says okay if it's one of these finitely many ones you give the the answer and that only affects the uh the running time by I guess a constant factor maybe at most so we we've shown a deterministic polomial time algorithm for the same language so L is also in P we started with arbitrary L in BPP and we've shown L is in P so the two are the I guess formally the other inclusion you'll show in the exercise. So for uh for the moment um since we uh somewhat at least I I I claimed that it's somewhat likely that these hard on average functions exist. Probably randomization alone will not help us solve NP hard problems.

15:17 Um, that's uh maybe a bad news, but I guess it's important to know because if you're if you're nothing's more frustrating than not so solving a certain task like uh designing an algorithm for a certain problem using a certain technique and then finding out that there's good evidence that what you tried is actually impossible. So I I I thought I want to spare you uh that frustration. And the second bit is this proof, the last proof we've done conceptually is not very hard. You just do this dandomization and then you observe well if the dandomization was very different from the actual random algorithm. Then the pseudo random bits were not actually behaving as random bits and so the whole thing breaks. The calculations are a bit tedious but the the intuition is isn't hard. So the the real heavy lifting seems all to be inside this pseudo random generator. Uh so I hope um I motivated you a bit to see to look inside uh what that does and dig a bit into uh the magic inside there.