Video 8-6: Nisan-Wigderson: Combinatorial designs

0:02 In the next section, we'll look at this construction from Nissan and Victorson to construct um a specific pseudo random generator. Uh we seem to have seemed to do all the heavy lifting in this previous observation that uh again just to mention that uh if we can get the construction in this section right, we have very strong evidence that BPP is the same as P. Again the intuitive version first is uh assuming we have some boolean function that has a a high circuit lower bound specifically this uh hard on average bound. Um the higher this function is then the more pseudo random bits we can pump out of this function around the same number of of truly random seat bits. And so uh the overall construction actually works even in weaker state with with weaker assumptions where this uh this hardness doesn't necessarily need to be exponential. If it's exponential we get the full result that we used and we can completely dandomize BPP. There's also potential parallel universes in between where we only know about somewhat weaker functions or somewhat weaker lower bounds on the circuit size of functions and then we can still get something. Uh my compromise for this section was to uh not show you the best possible construction for all these intermediate parallel universes, but rather uh focus on the most interesting case, namely that the full hypothesis is true and BP can be completely dandomized.

1:50 I think it's also fair to mention that Abby Vickerson won the touring award two years back uh among other things for these kind of results. I certainly worked on on many other things but uh randomization and de dandomization are one of the things that were mentioned in the latoio again shows the kind of impact that these these ideas had. Um now this section in specifically uh I think I'll exclude all the quantitative parts from the exam just because it gets a bit too crazy and annoying to memorize. I don't think that's so helpful and getting all the details right uh I don't think adds much. Um the the intuition and the qualitative ideas I think are are fine. uh you you should be able to get those uh reproduced but not the setting of the parameters and all these uh these bits.

2:55 Uh just to state um what in um Aurora and Barak's book is the the most sophisticated version of this result. So putting this into quantitative terms is what you get in this theorem. Uh if you have any function where the average case hardness is s then you could build from that uh a pseudo random generator that gets almost s uh but you have to uh take this some some constant delta where you uh take essentially the power to the delta in the end. So it makes it a little little less than s of L but reasonably close and good enough for our purposes. We not actually show this result in its generality. We'll show it but only for the specific case of our exponential S.

4:01 The key construction of Nissan and Victorson's generator is actually surprisingly simple. And um before going through the the formal definition, let me just say suppose you have seat bits, you line them up. There's always going to be L seed bits in the parameters that we we have. and we want to generate m output bits which is many many more exponentially more then um there's not so much you can do to get from from L to essentially exponential in L the only real construction you have at your disposal is take subsets and maybe that's intuitive enough so you take some subset of how can I draw this nicer uh You take some some subset of these.

5:04 Let me try to do it maybe like this. That's going to get one output bit by applying our function f. That's the key idea. Then you take some other set that gets another bit but again with function f. Now, this is going to go fine for some, but you'll not going to be able to uh avoid overlapping sets if you want an exponential size down here, right? There's not enough not enough bits in L. So, we'll have potentially overlapping subsets. Um and we'll take a whole family of subsets of uh the positions in L and we'll just output all of these the sequence of all of these uh subsets. So take the appropriate uh indices in the subset and feed that to your heart function f and that's your sequence of pseudo random bits.

6:06 I think after seeing it, it's almost is almost like uh how else would you do it? It seems like almost the only way that could potentially work. But of course uh the crucial ingredient here is this um this subset uh this collection of subsets. uh and also we somehow need to show that by doing this computation with overlapping sets we don't make the product the result too predictable otherwise it wouldn't be pseudo random.

6:46 So that step is maybe very natural. Uh but then the magic comes in the following steps and the key definition how they came up with this is not clear to me. Um the the key definition is to have the right restrictions on these subsets to make everything tick. Uh the general the general frame framework is well they called it combinatorial design which is a very non-telling term. Uh it's just a a collection of subsets from a set of size L. The seat bits each of the sets should have size n. In total we want m of these subsets and we want to use a very large m. And then there's a third parameter which is uh d and that's the bound on the intersections. So any two of these subsets should have at most d positions in common from the in total n. And uh in general it only makes sense if d is at most n obviously and n is at most l obviously but we'll we'll need some slack between those numbers uh for such a thing to exist. So this is just the definition that says if I have a collection of subsets satisfying these properties then I call it a combinatorial design. But you can easily pick parameters for ln n and d where no such thing exists.

8:16 And so we're we're uh with this we're skating at the boundary of of existence and the concrete set of parameters that always works uh are in in this lema. This is uh both existence but also an algorithm to compute uh such a design.

8:36 And it's a lovely kind of it's it's ironic that the algorithm itself uses dandomization but is based on a probabilistic method proof. Um that's somehow this could be from Ghabach. Um okay forget it. You'll maybe maybe you'll follow the joke after the uh proof. So we're given um the parameters n L and D as inputs and we're supposed to generate all these subsets. um because the output is so big, it's definitely going to take a while. Okay, so we allow ourself exponential time in L. That's fine. At the very end of the game, L will be logarithmic. So, uh no no no reason to worry. And the restrictions are that L needs to be substantially bigger than N. And the size the number of outputs and the number of of of uh sets in our output set that was called m before is 2 to the d over 10. Again these constants you can probably play with um but no need to.

9:42 What you don't yet know or what you cannot yet see is that these these sets of parameters will make for a suitable pseudo random generator. That's for tomorrow. Um, but I want to briefly show how to do this construction.

10:02 The algorithm is incredibly simple. We start with no sets and then we are bluntly iterating over all possible subsets and we pick the first that we can add to our set without violating any constraints. And the constraint that's relevant is essentially the uh uh the the intersection constraint. If I already have built a collection of some subsets in my calligraphic eye, then if I take a new subset, it might have too many indices in common with some previous set. But I'm I'm going to allow myself to run through all possible subsets. I have exponential time, so why not? and the first one that has a small enough intersection with all previous sets I'm going to take. So the only question this algorithm is obviously correct in that it never produces um an output that is not a a combinatorial design but the the key is is it possible that this algorithm finds enough sets? Why could it not possibly be uh running into a dead end and be stuck so that no no set can be added but we don't have the number of sets that we wanted.

11:16 So the the thing that we still need to show is that a always succeeds and look at the algorithm that there's no randomness. Okay, it's deterministic. It just does um essentially a brute force approach. But to prove that it works, we'll use the probabilistic method.

11:39 And uh I have only vaguely explained what that is before. So this is a good way to show you it what what it does in action. Uh we'll just instead of running the actual algorithm, we'll do instead of going over all subsets, we'll uh what we'll do is we generate a set at random and show that the probability that this succeeds is not zero. And that's the probabilistic method. That's all it does really. If you have some something to generate and there's a probability that the random object you do you build is is that object and the probability is greater than zero then such an object exists. Otherwise the probability had to be exactly zero. And here we have some uh some freedom. we pick um this random set for each position in in the allowable indices. We pick the position with probability 2 n / l. So on average we'll have uh 2 * n elements in the set but it's also random how many right but we uh we make the set we bias the set to be a bit bigger than we needed.

12:50 uh and then this is kind of exercise level uh and I'm I'm skipping the math this time. You can show with the standard turnoff bound because these are independent and with the same probability these are just binomial uh random variables these these uh involved sizes. Uh the probability that the set that you pick is way too small is very small. uh at least if if n is big enough certainly this is true um because you're expecting way more you expect 2 n um so half of that you'll most of the time have and also for any fixed uh set that you already have um the probability that you have a larger intersection with that set than d is exponentially small and that comes from this uh bound on uh on L. So in a way L is is so huge that if you only pick two N of the positions N here and N there the fact that many of them overlap is actually not likely.

14:04 Now that's for one specific set J. Um in the end our set capital I or calligraphic I will have a lot of these sets and uh we want that uh we don't have a large intersection with any of them. So this is the bad event that we have large intersection the union of all those bad events is that any of the events at least one bad thing happens. So we can use the union bound on on this um like uh we do the probability that I and a specific J have large intersection.

14:53 And so we take the union over all J in our calligraphic I and that's where we use the union bound. It's the size of I times the probability for this and that's the 12 2 minus D / 10. And then if you uh if you set plug that in this guy is less than or equal 2 the d / 10. That part just cancels and you get the 1/2 that we have here. So the probability that the new set does not intersect any of the sets at too many positions is uh at least 1/2. And if you take the two together, we want both of the good things at the same time. Uh we at least have a probability of 0.45 four five that the new random set is good that in the sense that it has small number of intersections with everything before and is large enough. Now it might be too large but that's actually you can just remove some of the positions until you're down to size n that can never add intersections and then you're done. So the the beauty why this analysis here is so easy is that because you're you're picking things independent independent and at random you uh establish exact and complete symmetry on this on this universe L so that it doesn't matter what the current sets look like you can upper bound the probability to intersect any of them uh in the same way.

16:37 So in each of the uh time in each of the steps where we add a new set we have some fixed probability to succeed. Now we need to succeed in every round. So actually this probability for m successes in a row is tiny but it is non zero and so some choice exists for the algorithm to pick and it'll just find it by brute force.

17:03 Okay, so that's the probabilistic method in action. Although we're analyzing a non-probabilistic algorithm or an key ingredient in building a pseudo random generator for dandrandomizing algorithms. Cool.