6.046J Lecture 22: Derandomization

Lecture 22 Derandomization Supplemental reading in CLRS: None Here are three facts about randomness: • Randomness can speed up algorithms (e.g., sublinear-time approximations) • Under reasonable assumptions, we know that the speed-up can’t be too large. Advances in complexity theory in recent decades have provided evidence for the following conjecture, which is generally believed to be true by complexity theorists:1 Conecture. Suppose there exists a randomized algorithm A which, on an input of size n, runs in time T and outputs the correct answer with probability at least 2/3. Then there exists a deterministic algorithm A 0 which runs in time Poly(n, T) and always outputs the correct answer. • In practice, randomization often doesn’t buy any (or much) speed-up. Moreover, the randomized algorithm is often based on novel ideas and techniques which can equally well be used in a deterministic algorithm. As we said in Lecture 9, a randomized algorithm can be viewed as a sequence of random choices along with a deterministic algorithm to handle the choices. Derandomization amounts to deterministically finding a possible sequence of choices which would cause the randomized algorithm to output the correct answer. In this lecture we will explore two basic methods of derandomization: 1. Conditional expectations. As we walk down the decision tree (see Figure 22.1), we may be able to use probabilistic calculations to guide our step. In this way, we can make choices that steer us toward a preponderance of correct answers at the bottom level. 2. Pairwise independence. Another way to find the correct answer is to simply run the randomized algorithm on all possible sequences of random choices and see which answer is reported most often (see Figure 22.2). In general this is not practical, as the number of sequences is exponential in the number of random choices, but sometimes it is sufficient to check only a relatively small collection of sequences (e.g., those given by a universal hash family). In what follows, we will use the big-cut problem to explore each of these two methods of derandomization: 1 See, for example, Impagliazzo and Wigderson, “P = BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma” 〈http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf〉. head head . . . tail tail head etc. tail . . . ··· Possible outputs, with correct outputs more concentrated in some regions than in others. Figure 22.1. Probabilistic computations can often be used as a heuristic to find the regions in which correct answers are most concentrated. Lec 22 – pg. 2 of 5 input · · · (true randomness)· · · 0000110010 · · · algorithm output input 1110110110 1101000010 0001110111 uniform among N possible strings algorithm 1011101010 0100110101 output Figure 22.2. Sometimes the deterministic component of a randomized algorithm can’t distinguish between a truly random sequence of choices and a well-chosen pseudorandom sequence of choices. Or, sometimes we can simulate a random choice from a large sample set (e.g., the set of all binary strings) using a random choice from a small sample set (e.g., a fixed set of N binary strings). If we can do this with N sufficiently small, it may be feasible to find the answer deterministically by running the randomized algorithm on all N of the possible random inputs. Lec 22 – pg. 3 of 5 Problem 22.1 (Big Cut). Given an undirected graph G = (V, E) with no loops, find a cut (S, V \ S) which crosses at least half of the edges in E. The solution to this problem is approximated by a simple randomized algorithm: Algorithm: 1 2 3 4 5 S←; for each v ∈ V do Flip a coin If heads, then S ← S ∪ {v} return (S, V \ S) The running time is Θ(V ). Proof of approximation. For each edge (u, v) ∈ E, we have · ¸ £ ¤ 1 (u ∈ S and v ∉ S) or Pr (u, v) crosses the cut = Pr = . (u ∉ S and v ∈ S) 2 Thus, if I (u,v) denotes the indicator random variable which equals 1 if (u, v) ∈ S, then we have " # X X ¯ ¯ £ ¤ £ ¤ E # edges crossed by S = E I (u,v) = E I (u,v) = 1 ¯E ¯ . (u,v)∈E (u,v)∈E 2 Chernoff’s bound then tells ¯ ¯ us that, when E is large, it is extremely likely that the number of edges crossed is at least 0.499 ¯E ¯. 22.1 Using Conditional Expectation We can deterministically simulate the randomized approximation to Problem 22.1 by choosing to include a vertex v if and only if doing so (and making all future decisions randomly) would result in a higher expected number of crossed edges than choosing to exclude v. In more detail, say V = {v1 , . . . vn }, and suppose we have already decided whether S should contain each of the vertices v1 , . . . , vk . We pretend that all future decisions will be random (even though it’s not true), so that we can use probabilistic reasoning to guide our choice regarding vk+1 . Ideally, our choice should maximize the value of ¯ £ ¤ E # edges crossed ¯ our existing decisions about v1 , . . . , vk+1 . (22.1) future random choices Consider the partition E = E1 t E2 t E3, where © ª E 1 = (v i , v j ) ∈ E : i, j ≤ k © ª E 2 = (v i , vk+1 ) ∈ E : i ≤ k © ª E 3 = (v i , v j ) ∈ E : j > k + 1 . Whether we choose to include or exclude vk+1 from S, the number of crossed edges in E 1 is unaffected. Moreover, since each edge in E 3 has at least one of its vertices yet to be randomly assigned to S or Lec 22 – pg. 4 of 5 V \ S, the expected number of crossed edges in E 3 is 21 |E 3 | regardless of where we decide to put vk+1 . So in order to maximize (22.1), we should choose to put vk+1 in whichever set (either S or V \ S) produces more crossings with edges in E 2 . (It will always be possible to achieve at least 12 |E 2 | crossings.) We can figure out what the right choice is by simply checking each edge in E 2 . £ ¤ Proceeding in this way, the value of E # edges crossed starts at 12 |E | and is nondecreasing with each choice. Once we make the nth choice, there are no more (fake) random choices left, so we have ¡ 22.2 ¢ £ ¤ # edges crossed = E # edges crossed ≥ 1¯ ¯ 2 E . ¯ ¯ Using Pairwise Independence The sequence of random choices in the randomized approximation to Problem 22.1 is equivalent to picking the set S uniformly at random from the collection S = P (V ) of all subsets of V . In hindsight, the only reason we needed randomness was to ensure that £ ¤ 1 Pr S doesn’t cross (u, v) ≤ S ∈S 2 for each (u, v) ∈ E. (22.2) Recall from §10.1 that a subset of V can be represented as a function V → {0, 1}. In this way, S becomes a hash family H : V → {0, 1}, and (22.2) becomes £ ¤ 1 Pr h(u) = h(v) ≤ h∈H 2 for each (u, v) ∈ E. This will be satisfied as long as H is universal. So rather than taking H to be the collection {0, 1}V of all functions V → {0, 1}, we can take H to be a much smaller universal hash family; there exist universal hash families of size O(V ).2 In this way, we have · E h∈H ¸ # edges crossed by the ≥ cut corresponding to h 1¯ ¯ 2 E . ¯ ¯ In particular, this guarantees that there exists some h ∈ H such that ¶ # edges crossed by the ≥ cut corresponding to h µ 1¯ ¯ 2 E . ¯ ¯ We can simply check every h ∈ H until we find it. Exercise 22.1. What are the running times of the two deterministic algorithms in this lecture? 2 One such universal hash family is described as follows. To simplify notation, assume V = {1, . . . , n}. Choose some prime p ≥ n with p = O(n) and let © ª H = h a,b : a, b ∈ Z p , a 6= 0 , where h a,b (x) = (ax + b) mod p. Lec 22 – pg. 5 of 5