CS787: Advanced AlgorithmsScribe: Yudong Tang and Baris Aydinlioglu Lecturer: Shuchi ChawlaTopic: Randomized Algorithms Date: September 17, 2007In this lecture and the next we cover randomized algorithms. Today we begin by motivating theuse of randomized algorithms. Next we recall some related definitions and results from probabilitytheory. We end today’s lecture with studying Karger’s randomized algorithm for computing amin-cut of a graph.6.1 IntroductionWe define a randomized algorithm as an algorithm that can toss coins and act depending on theoutcome of those tosses. There are two kinds of randomized algorithms that we will be studying:• Las Vegas Algorithms: These refer to the randomized algorithms that always come up witha/the correct answer. Their “expected” running time is polynomial in the size of their input,which means that the average running time over all possible coin tosses is polynomial. Inthe worst case, however, a Las Vegas algorithm may take exponentially long. One exampleof a Las Vegas algorithm is Quicksort: it makes some of its decisions based on coin-tosses,it always produces the correct result, and its expected running and worst-case running timesare n log n and n2, respectively.• Monte Carlo Algorithms: These refer to the randomized algorithms that sometimes comeup with an incorrect answer. Like Las Vegas algorithms their expected running time ispolynomial but may be exponential.By performing independent runs of a Monte Carlo algorithm, we can decrease the chances ofobtaining an incorrect result to a value as small as we like. For example, if a particular MonteCarlo algorithm produces an incorrect result with probability 1/4, and we have the abilityto detect an incorrect result, then the probability of not obtaining a correct answer after tindependent runs is (1/4)t. In some contexts, such as in optimization problems, we do nothave the ability to detect an incorrect answer, but can compare different answers and pickthe best one. The same analysis would also apply in these cases, because if picking the bestanswer does not give the optimal answer, then it means the algorithm produced an incorrectanswer in all of its independent runs.Sometimes we may not have an algorithm with an error probability of a small constant, butwe may have one with error probability a function of the input size. In such a case, we aimfor an error probability from which we can obtain desired low values with a small number(i.e., polynomial in the size of the input) of independent runs.6.2 MotivationRandomized algorithms have several advantages over deterministic ones. We discuss them here:1• Randomized algorithms tend to bring simplicity. For example, recall from Lecture 2 theproblem of finding the kth smallest element in an unordered list, which had a rather involveddeterministic algorithm. In contrast, the strategy of picking a random element to partitionthe problem into subproblems and recursing on one of the partitions is much simpler.• Another advantage randomized algorithms can sometimes provide is runtime efficiency.Indeed, there are problems for which the best known deterministic algorithms run in ex-ponential time. A current example is Polynomial Identity Testing, where given a n-variatepolynomial f of degree d over a field F, the goal is to determine whether it is identically zero.If f were univariate then merely evaluating f at d + 1 points in F would give us a correctalgorithm, as f could not have more that d roots in F. With n variables, however, there maybe ndroots, and just picking nd+ 1 points in F gives us exponential time. While we don’tknow of a deterministic polytime algorithm for this problem, there is a simple algorithm thatevaluates f at only 2d points, based on a theorem by Zippel and Schwarz.A prevalent example where randomization helps with runtime efficiency used to be Primalitytesting, where given an n-bit number, the goal is to determine if it is prime. While straightfor-ward randomized algorithms for this problem existed since the 70’s, which ran in polynomialtime and erred only if the number was prime, it was not known until two years ago whethera deterministic polytime algorithm was possible—in fact, this problem was being viewed asevidence that the class of polytime randomized algorithms with one-sided error is more pow-erful than the class of polytime deterministic algorithms (the so called RP vs P question).With the discovery of a polytime algorithm for Primality, however, the question still remainsopen and can go either way.• There are problems in which randomized algorithms help us where deterministic algorithmscan provably not work. A common feature of such problems is lack of information. Aclassical example involves two parties, named A (for Alice) and B (for Bob), each in possessionof an n bit numb er (say x and y resp.) that the other does not know, and each can exchangeinformation with the other through an expensive communication channel. The goal is to findout whether they have the same number while incurring minimal communication cost. Notethat the measure of efficiency here is the number of bits exchanged, and not the runningtime. It can be shown that a deterministic protocol has to exchange n bits in order to achieveguaranteed correctness. On the other hand, the following randomized protocol, based on theidea of fingerprinting, works correctly with almost certainty: A picks a prime p in the range[2n, 4n] at random, computes x mod p, and sends both x and p to B, to which B respondswith 1 or 0 indicating whether there was a match. With only O(log n) bits exchanged, theprobability of error in this protocol–i.e., Pr[x 6= y and x mod p = y mod p]– can be shownto be at most 1/n. By repeating the protocol, we can reduce the probability of an error toless than that of an asteroid colliding with either of A or B’s residences, which should be apractically sufficient threshold.We now list several more examples of tasks where randomization is useful:Load Balancing: In this problem there are m machines and incoming jobs, and the goal is toassign the jobs to the machines such that the machines are equally utilized. One simple way that2turns out very effective here is to simply pick at random, given a job, one of the m machines andassign the job to it. We will study load balancing in a later lecture.Symmetry Breaking: Randomization comes handy also in designing contention resolution mech-anisms for distributed protocols,