18.405J Lecture 21: P vs BPP 2

-- Advanced Complexity Theory Lecture 21: P vs BPP 2 1 Overview In the previous lecture, we began our discussion of pseudorandomness. We presented the BlumMicali definition of a pseudorandom generator, which defines pseudorandomness in terms of how hard it is for members of a specific computation class to distinguish between true randomness and generated randomness. We proved Yao’s theorem, which provides a link between the existence of certain pseudorandom generators and the equivalence of certain complexity classes. Finally, we presented the Nisan-Wigderson pseudorandom generator which (if the Nisan-Wigderson assumption holds) will imply that BP P = P . In this lecture we will complete the proof that the Nisan-Wigderson assumption implies that BP P = P . We will then discuss the relation between worst case hardness and average case hardness, and present a hardness amplification result due to Sudan, Trevisan, and Vadhan based on error correcting codes. 2 Nisan-Wigderson Generator We begin by reviewing the notation of the previous lecture. Recall that a function f : {0, 1k → {0, 1} is -easy for circuits of size m if there exists a circuit C of size at most m such that Prx←{0,1}k [f (x) = C(x)] ≥ 1 + 2 The Nisan-Wigderson assumption is that there exists an f : {0, 1}k → {0, 1} such that f is computable in time 2O(k) but such that f is not -easy for circuits of size 22δk (for some constant δ). If such a function exists, we can construct the following pseudorandom generator. Fix s = Θ(log n) and n subsets T1 , T2 , . . . , Tn ⊂ {1, 2, . . . , s} such that |Ti | = k for each i. Our generator G is then the function from {0, 1}s to {0, 1}n defined by G(z)i = f (z|Ti ) where z|Ti is the k-bit string formed by restricting z to the indices in Ti . In our proof last lecture, we defined the n + 1 hybrid distributions Hi for 0 ≤ i ≤ n, where Hi is the distribution resulting from concatenating the first i digits of G(z) (for uniformly chosen z) with a uniformly chosen string of length n − i. Then, if G is not a pseudorandom generator, there is a distinguisher D of size less than size 22δk such that 1 Prz ←{0,1}s [D(G(z)) = 1] − Prny∈{0,1 [D(y) = 1] >  If we then let αi = Prw←Hi [D(w) = 1], then this condition is simply that αn − α0 > . By the pigeonhole principle, there must exist an i such that αi − αi−1 > /n. We will show that this results in a contradiction; specifically, we will construct a small circuit that approximately solves f , which contradicts our hardness assumption. In the previous lecture, we showed how to prove this for i = 1. In this lecture, we will show how to extend this to arbitrary i. Let y be a random n bit string; then we can write the claim αi − αi−1 > /n as: Prz,y [D(f (z|T1 ), . . . , f (z|Ti ), yi+1 , . . . , yn ) = 1] − Prz,y [D(f (z|T1 ), . . . , yi , yi+1 , . . . , yn ) = 1] >  n Since pseudorandomness is equivalent to unpredictability (a simple corollary of Yao’s theorem), the above claim holds iff there exists a circuit D0 (about as large as D) such that Prz [D0 (f (z|T1 ), f (z|T2 ), . . . , f (z|Ti−1 )) = f (z|Ti )] ≥ 1  + 2 n Note that the right hand side of D0 (f (z|T1 ), f (z|T2 ), . . . , f (z|Ti−1 )) = f (z|Ti ) only depends on z |Ti . Therefore, letting T¯i be the complement of Ti in {1, . . . , s}, by the averaging principle, there must be a setting for z|T̄i such that the claim still holds. Fixing z|T¯i to this setting, we can write fj (z|Ti ∩Tj ) = f (z |Tj ) for 1 ≤ j < i. Our claim then becomes: Prz |Ti [D0 (f1 (z|T1 ∩Ti ), f2 (z|T2 ∩Ti ), . . . , fi−1 (z|Ti−1 ∩Ti )) = f (z|Ti )] ≥  1 + 2 n Now, we wish to compute f (z 0 ) easily. To achieve this, we will choose our sets Ti so that all the intersections Ti ∩ Tj are small. Then, since any function on ` variables can be simulated by a circuit of size `2` , if these intersections are small then we should be able to easily simulate all of the functions fj . In particular, if |Ti ∩ Tj | ≤ δk, then there exists a circuit D00 of total size iδk2δk + |D0 | ≤ 22δk which satisfies Prz |T [D00 (z|Ti ) = f (z |Ti )] ≥ i 1  + 2 n But this contradicts our hardness assumption for f ! Therefore, as long as we can show that such sets Ti exist, then our main result follows. In particular, we must show the following lemma. 2 Lemma 1. For every positive k and δ, there exists an s = O(k/δ) and n = 2Ω(δ k) and sets T1 , ..., Tn ⊂ {1, . . . , s} such that |Ti | = k and |Ti ∩ Tj | ≤ δk. Moreover, we can find such a set in polynomial time. Such collections of subsets are known as combinatorial designs. There exists a simple greedy algorithm for finding such sets; for more details, interested readers should consult Section 20.2 of the class textbook. 2 3 Worst case versus average case hardness Most of the time in theoretical computer science, we are concerned with worst case hardness; for example, when we talk about algorithms, we often measure their efficiency by their worst-case running times, and hard problems like SAT need only be hard in the worst case. In our discussion of pseudorandomness above, we needed problems that are hard not just in the worst-case, but in the average-case. For example, our definition of a function being -easy to compute was in terms of the probability over random k-bit strings chosen uniformly at random. In order to prove the validity of the Nisan-Wigderson assumption, we will therefore need problems that are not just hard in the worst case, but hard in the average case. 3.1 The Permanent Unfortunately, it turns out that it is usually much harder to prove claims about average case complexity than it is to prove claims about worst case complexity. One problem that we can prove average case complexity claims about is the problem of computing the permanent of a matrix. Definition 2. If M is an n by n matrix with entries Mij , the permanent of M is given by perm(M ) = n XY Miπ(i) π i=1 where the sum is over all n! permutations of the numbers 1 through n. Note that the above formula for the permanent is very similar to the Leibniz formula for the determinant, the exception being that each product has an additional (−1)sgn(π) factor. However, while the determinant can be computed in polynomial time (via Gaussian elimination, for example), the permanent is very hard to compute. It is known (due to a theorem of Valiant) that computing the permanent is #P complete [4]. It turns out (due to an argument of Lipton) that computing the permanent is also hard on average. In particular, we have the following theorem. Theorem 3. If algorithm A computes perm(M ) mod p in expected time t(n) when M is uniformly chosen at random from Zn×n , then there exists a probabilistic algorithm that computes the permap nent perm(M ) on all M in time Θ(nt(n)) Proof. See [4]. Based on this observation, we might wonder whether we can link average-case hardness to worstcase hardness in any other situations. 3.2 Hardness Amplification and Error Correcting Codes Recall that E is the complexity class given by DT IM E(2O(n) ). The following theorem is due to Sudan, Trevisan, and Vadhan. 3 Theorem 4. ([3]) If there exists an f : {0, 1}∗ → {0, 1} such that f ∈ E and f is not computable in size 2δn , then there exists a function f˜ such that f˜ ∈ E but f˜ is not -easy to compute in size poly()2δn . Note that this essentially says that if we have a function that is hard to compute in the worst-case (not computable in size 2δn ) then it is approximately as hard to compute in the average case (not -computable in size poly()2δn ). The proof of this theorem is based on the theory of error-correcting codes. Definition 5. A τ -error-correcting code is a pair of functions E : {0, 1}k → {0, 1}n and D : {0, 1}n → {0, 1}k that satisfy the relation D(E(x) ⊕ η) = x ∀η ∈ {0, 1n s.t.wt(η) ≤ τ n . Here ⊕ is the XOR operation, and wt(s) for a binary string s is equal to the number of bits in s set to 1. As suggested by the name, error-correcting codes are primarily used to store information with some redundancy so the information is resilient to some amount of noise. For example, for a τ error-correcting code, if you toggle at most a fraction of τ of the bits after you encrypt a piece of information, then you can still extract the original message. Clearly n must be larger than k. A simple information theoretical argument shows that, for a τ -error-correcting code n must be at least k/(1 − H(τ )), where H(τ ) = −τ log τ − (1 − τ ) log(1 − τ ) is the one-bit information entropy of τ (the Gilbert-Varshamov Bound further shows that such codes exist for all τ < 1/2). Since H(1/2) = 1, this bound also shows that codes can only exist for τ < 1/2. It is easy to see that in general, codes cannot exist for τ > 1/2; in particular, since two n-bit words w1 and w2 can disagree in at most n bits, by toggling the first half of these bits we have a word w0 that is within Hamming distance n/2 of both w1 and w2 . For our purposes, we also want E and D to be computable in polynomial time. For all τ < 1/4, there are known explicit constructions of polynomial-time-computable τ -error correcting codes with n = O(k). It turns out that it is very hard to beat the τ = 1/4 barrier. We will therefore consider the following relaxed definition of an error correcting code (known as a list decodable code). Definition 6. A (τ, L)-error-correcting code is a pair of functions E : {0, 1}k → {0, 1}n and D : {0, 1}n → {{0, 1}k }L such that 4 x ∈ D(E(x) ⊕ η) ∀η ∈ {0, 1}n s.t.wt(η) ≤ τ n . In particular, our local decoder D now generates L possible messages, and we only require that the actual message belongs to this set. For these error-correcting codes, the following theorem is known. Theorem 7. For every τ ≤ 1/2 − , there exists a polynomial-time computable (τ, L = O(1/2 )) error-correcting-code with n = O(k/3 ). The rough idea is that to transform a worst-case hard function f to an average-case hard function f˜, we treat the truth table of f as a message that is to be encoded using an error correcting code. The encoded version then is the truth table of an average-case hard function f˜. To prove average-case hardness, one shows that any efficient algorithm A that solves f˜ on a 1/2 +  fraction of inputs can be treated as a “corrupted” version of f˜, and then combined with a decoding procedure, f can be computed exactly using the efficient algorithm – which would contradict worst-case hardness of f . However, even list decoding is not enough for this process to work; we require that the decoding procedure runs extremely efficiently (so that A combined with the decoding procedure is still efficient). Thus we need a stronger notion called local list decoding, where the decoding procedure runs in sublinear time (it doesn’t need to read the the entire codeword in order to decode the message). We refer the readers to [3] for more details. We can now provide a proof sketch of Theorem 4. Proof of Theorem 4. Let (E, D) be a 1/2 −  local list-decoding code (for some  to be determined later) whose decoder runs in sublinear time, where E : {0, 1}K → {0, 1}N , with K = 2k . Then a function f : {0, 1}k → {0, 1} can be viewed as a K-bit string and thus and element of the domain of E. E(f ) is then an N -bit string, which can be interpreted as the truth table of a function f˜ : {0, 1}n → {0, 1}. Since f˜ is some function on n binary inputs, it can be computed in time 2O(n) and therefore f˜ ∈ E. We need to show that this f˜ is hard to -approximate. Note that if you can compute an  approximation to f˜, then the decoder D will be able recover f exactly. This means that if f is hard, then f˜ should be hard to approximate, which is exactly the statement that we want. References [1] R. Lipton, New directions in testing, Distributed Computing and Cryptography, 2:191-202, 1991. [2] N. Nisan, A. Wigderson, Hardness vs randomness, Journal of Computer and System Sciences, 49(2):149-167, 1994. [3] M. Sudan, L. Trevisan, and S. Vadhan, Pseudorandom generators without the XOR lemma J. Comput. Syst. Sci., 62(2):236-266, 2001. 5 [4] L. G. Valiant, The Complexity of Computing the Permanent, Theoretical Computer Science 8(2):189201, 1979. 6