Video 7-1: Randomization motivation

0:02 The next unit starts the I guess second big part of the lecture where we uh give up some of the um correctness criterion for our algorithms uh and try to get get further speed ups by doing so. uh this will keep us busy for a while and in the first bit we'll kind of set set the stage mostly for the algorithms um with a few uh examples and and basically as some some terminology uh so I I'll give a little bit of of motivation and maybe a a deep dive in one specific topic just to make a point uh might keep us busy for today and then um we'll revisit a bit of the the background What's this about? Well, uh if we're faced with an heart optimization problem or an NP heart decision problem and all the known algorithms that uh we can think of still don't really uh help us in that they're still too slow. The only way for forward seems to be to uh make compromises on on what we want. Classical algorithms as we've studied them in fixed parameter attractability have to be always and exactly correct and really think of a exactly makes sense for for optimization problems more than for decision problems. Uh but really these are these are two separate properties and we could give up either of them or both. And here we'll give up the first one, namely that the algorithms always work or provably always work. And uh I guess the opposite of that is that they can occasionally fail. Now that sounds not too good. So we'll have to make sure that fail is uh in a specific way. Um for a deterministic algorithm, what fail means is that on some inputs it doesn't work. That's the only thing it it could mean because it has to do the same steps on the same input each time you run it. Uh and that's maybe not so satisfying because if your input is one of those that your algorithm fails on, you're still out of luck. So in a way it's it's clear we have to do something that even if I give you the same input again, the next time you run the algorithm, something different will happen. And that's what we call non-determinism because the algorithm is not deterministic or the computation is not fully determined just by the algorithm and the input. On the other hand, I've marketed non-determinism when we discussed traditional complexity as something that's completely unrealistic and useless in practice and just a hypothetical thing you can compete with.

3:00 So we won't we won't use general non-deterministic Turing machines here. uh but I think it's useful to think of randomization as a specific way of non-determinism but one where you have control over how likely things are and formally it'll look quite different but I think this is still the way to uh to kind of see what um what fail means um we use random bits to guide the computation so there's some some assumed um module of the machine that can generate randomness and we won't discuss much uh what you can do there in practice but this is this is in both is both a solved problem and kind of not a problem and a big problem depending on what exactly you need. Uh getting some random bits is not not that hard. Um you can measure the resistance of uh the the voltage of some resistor. There's some randomness in there just from at the end of the day quantum physics and you can uh calculate random bits from that from there and they're true random bits for all that we know. Uh on the other hand if you have very specific requirements and in particular if you need a lot of random bits in a short time you might have to do something smarter.

4:24 We'll come back a little bit on that but uh for our computational model mostly we'll just assume that there's some random bits. Now the point of uh of randomization is that instead of failing on some rare inputs that might still be the ones we care about, we rarely fail or any specific input and by repeating we can make it rarer. Okay.

4:57 Why could this possibly be useful? Um allowing something to fail. I mean, apart from making things worse. Um there's a there's some somewhat distinct reasons why this can make life easier for designing algorithms. Uh and we'll see examples of each, but maybe it's it's useful um to already kind of distinguish them first. Uh it often makes algorithms simpler. And simp simple is um is a complicated term. Um I'm currently program committee chair for a track of an algorithms conference that specifically invites simple algorithms or simple proofs of existing algorithms. This is actually a tricky problem. What what does simple mean in the eye of the beholder? Uh but when you see examples maybe you can agree that some are indeed simpler than than the alternative that cannot use randomness. And uh intuitively for me uh you can avoid certain dealing with the full uh generality of the problem by uh by randomization often allows you to get away with the usual case. If you can get that to work, then randomization can sometimes uh do the rest. A totally different reason why randomization and specifically this being correct most of the time but not strictly always can help is the idea of fingerprinting or maybe check sums would be a better term.

6:28 fingerprinting kind of got stuck but it's the wrong metaphor because from all I know uh human fingerprints are actually unique in or close to you can identify an individual human being by the fingerprints and this is totally not the idea of what fingerprints are used in computation or in algorithms there the idea is you take this complicated thing the full human being maybe the full genome and you reduce it to something much simpler and smaller that's quicker to compare. That's the way the metaphor is is to be taken. Uh so instead of um answering the bull question, you answer a cheap surrogate question. But sometimes you have uh false positives. Um I mean the other thing this is also called hashing uh is um the same the implementation of fingerprinting usually is hashing and that's what check sums also are uh in some form or another. So check sums you would say if you if you want to know if two files long big files are the same you could compute some good check sum and if the check sums the same chances are good the files are also the same.

7:42 it's unlikely that there's a a collision with different files giving the same check sums. That's a a specific technique, but it's helpful so often that uh I made it a bullet of its own. And then the other um the other reason is a bit more more subtle. Maybe uh we'll we'll see this today is sometimes you can um you can prove lower bounds for algorithms by constructing an adversary that tries to make the algorithm fail by kind of modifying the input along the way. And by throwing in randomness in the algorithm, you make the algorithm itself less predictable. And so the adversary has power. And uh that could mean that you can actually get stronger results. Typically you can find faster algorithms or or less costly algorithms using randomization. And you can prove any deterministic algorithm has to pay strictly more.

8:43 There's um another uh use case for randomization which is uh also using randomized algorithms but in a way has an entirely different goal of its own and that's often called uh the probabilistic method and this has virtually nothing to do with um solving optimization problems and so on. uh rather you have some obscure uh object or a prop object with certain properties where it's not obvious or not clear whether it should exist. And uh the idea is the proof technique says okay maybe you don't know let's try to design a randomized algorithm to construct such an object or to find such an object and if you can prove that there's a positive nonzero probability that this algorithm succeeds well then there must be such an object. Uh the trick here is that oftenimes this is much easier. There's various techniques um and it's non-constructive. It doesn't tell you how to exactly find this object or what it exactly looks like. It just proves that there is one. And um because that's that's probably a bit abstract. Um I think it might be nice to have a a specific example and that that was taken from Ramsey theories is kind the whole a whole area of specific discrete math results of this sort. Um really the uh the gist of it is is just this. You start with an a complete graph on some number of vertices. And now um I'm coloring the edges either red or blue. So every edge gets some color.

10:54 And I'm doing this uh I mean this is um very color. And the claim is you can always find a click of vertices that have all edges in the same color of size at least um some bound that depends on n. And uh this is this is um a lot of open problems connected to how exactly this r of n looks like. But I think you could take login as a lower bound. Uh I should have looked this up. So in in my example, there's um a triangle of of the same color, for example, this red one. And I mean, if you think about this, of course, you can you can try to reason about this in in various ways.

12:24 Um the but for for graph of of size of size five is it always possible to find a triangle of uh the same color is at least not obvious right um it's not so clear. Uh the idea of of the probabilistic method would now be uh to say let's um let's design a randomized algorithm to find such a such um such an edge. And so I'm I'm starting with the uncolored graph. I'm randomly coloring the edges and then I'm trying to calculate the probability that my algorithm succeeds in finding such a a monochromatic click. And uh you can you can then reason over this algorithm a bit easier that say the expected number of such things it finds is strictly greater than zero so there must be one okay that um the analysis uses things I'm I'm going to introduce later so I'm not going to do this now but that's kind of uh the uh the idea of what this probabilistic method looks like and often times you this is the only way we know to prove the existence of certain objects. Uh which is pretty cool. On the other hand, it's also unsatisfying because it doesn't allow us to construct these objects. It just tells us that they exist. There's an obvious um similarity between randomization and average case analysis.

14:03 And this is really a undergraduate uh repetition that uh a good undergrad algorithms course will have drilled into you but it's worth stating again just to make the distinction clear. Uh average case analysis can talk about deterministic or randomized algorithms but let's suppose the algorithm is deterministic. Um so the same input leads to the same computation. I can still ask what happens for an average input. Uh randomized algorithms, the algorithm itself is not deterministic. It involves randomness and it generates the randomness. So it even on the same input does different computational steps. Um average case analysis says okay the input is random and it's coming from some distribution. In randomized algorithms, our usual type of analysis at least will be worst case. We assume the input is the worst possible. But then we uh throw our random bits on it. And I guess uh it might be useful to say here explicitly that uh because that term is also used sometimes. The adversary we imagine here is oblivious to our random bits. The person choosing the worst case input doesn't know what random bits we have. Uh it's kind of logical because they're random, right? So how could they know them? But in in in theory, you could imagine that someone also can look at your random bits. And this is important to point out here they cannot. at least they can't uh decide they can choose the input based on the random bits. And then if we analyze things um the cost is given as an expected value.

16:15 If you do average case analysis but the expectation is over the different types of inputs. If you do a randomized algorithm and worst case analysis then the cost is also an expectation but the expectation is over the random choices of the algorithm. So it's um is a different beast altogether but uh the analysis techniques might still be very similar just because the randomized algorithm might effectively force the input to look like a random input. And so I guess here one algorithm might first shuffle the input to produce a clearly uniformly random permutation and then it sorts. That's actually not a stupid idea in quicksort. Instead of picking random pivots in each step, you might uh it's easier to program at least to first shuffle the entire list and then sort it afterwards. And then the sorting step can use standard choice of the pivot maybe the first or last element and nothing bad will happen most of the time.