i Computational Complexity: A Modern Approach Draft of a book: Dated January 2007 Comments welcome! Sanjeev Arora and Boaz Barak Princeton University [email protected] Not to be reproduced or distributed without the authors’ permission This is an Internet draft. Some chapters are more finished than others. References and attributions are very preliminary and we apologize in advance for any omissions (but hope you will nevertheless point them out to us). Please send us bugs, typos, missing references or general comments to [email protected] — Thank You!! ii Chapter 13 Communication Complexity Communication complexity concerns the following scenario. There are two players with unlimited computational power, each of whom holds an n bit input, say x and y. Neither knows the other’s input, and they wish to collaboratively compute f(x,y) where the function f:{0,1}n×{0,1}n → {0,1}isknowntoboth. Furthermore, theyhadforeseenthissituation(e.g., oneofthepartiescould be a spacecraft and the other could be the base station on earth), so they had already —before they knew their inputs x,y— agreed upon a protocol for communication.1 The cost of this protocol is the number of bits communicated by the players for the worst-case choice of inputs x,y. Researchers have studied many modifications of the above basic scenario, including randomized protocols, nondeterministic protocols, and average-case protocols. Furthermore, lower bounds on communication complexity have uses in a variety of areas, including lower bounds for parallel and VLSIcomputation,circuitlowerbounds,polyhedraltheory,datastructurelowerbounds,andmore. In this chapter we only give a very rudimentary introduction to this area. In Section 13.1 we provide the basic definition of two-party deterministic communication complexity. In Section 13.2 we survey some of the techniques used to prove lower bounds for the communication complexity of various functions, using the equality function (i.e., f(x,y) = 1 iff x = y) as a running example. In Section 13.3 we define multiparty communication complexity and show a lower bound for the generalizedinnerproductfunction. Section 13.4 containsabriefsurveyofothermodelsstudied, in- cluding probabilistic and non-deterministic communication complexity. The chapter notes mention some of the many applications of communication complexity. 13.1 Definition of two-party communication complexity. Now we formalize the informal description of communication complexity given above: 1Do not confuse this situation with information theory, where an algorithm is given messages that have to be transmitted over a noisy channel, and the goal is to transmit them robustly while minimizing the amount of com- munication. In communication complexity the channel is not noisy and the players determine what messages to send. p13.1 (241) p13.2 (242) 13.2. LOWER BOUND METHODS Definition 13.1 (Two party communication complexity) Letf : {0,1}2n → {0,1}beafunction. At-roundtwopartyprotocolΠforcomputing f is a sequence of t functions P ,...,P : {0,1}∗ → {0,1}∗. An execution of Π on 1 t inputs x,y involves the following: Player 1 computes p = P (x) and sends p 1 1 1 to Player 2, Player 2 computes p = P (y,p ) and sends p to Player 1, and so on. 2 2 1 2 Generally,attheith round,ifiisoddthenPlayer1computesp = P (x,p ,...,p ) i i 1 i−1 and sends p to Player 2, and similarly if i is even then Player 2 computes p = i i P (y,p ,...,p ) and sends p to Player 1. i 1 i−1 i The protocol Π is valid if for every pair of inputs x,y, the last message sent (i.e., the message p ) is equal to the value f(x,y). The communication complexity of Π t is the maximum number of bits communicated (i.e., maximum of |p |+...+|p |) 1 t over all inputs x,y ∈ {0,1}n. The communication complexity of f, denoted by C(f) is the minimum communication complexity over all valid protocols Π for f. For every function, C(f) ≤ n+1 since the trivial protocol is for first player to communicate his entire input, whereupon the second player computes f(x,y) and communicates that single bit to the first. Can they manage with less communication? Example 13.2 (Parity) Suppose the function f(x,y) is the parity of all the bits in x,y. Then C(f) = 2. Clearly, C(f) ≥ 2 since the function depends nontrivially on each input, so each player must transmit at least one bit. The fact that C(f) ≤ 2 is demonstrated by the following protocol: Player 1 sends the parity a of the bits in x and Player 2 sends a XOR’d with the parity of the bits in y. Example 13.3 (Halting Problem) Consider the function H:{0,1}n×{0,1}n → {0,1} defined as follows. If x = 1n and y = code(M) for some Turing Machine M such that M halts on x then H(x,y) = 1 otherwise H(x,y) = 0. The communication complexity of this is at most 2; first player sends a bit indicating whether or not his input is 1n. The second player then determines the answer and sends it to the first player. This example emphasizes that the players have unbounded computational power, including ability to solve the Halting Problem. Sometimes students ask whether a player can communicate by not saying anything? (After all, they have three options in each round: send a 0, or 1, or not send anything.) We can regard such protocols as having one additional bit of communication, and analyze them analogously. 13.2 Lower bound methods Now we discuss methods for proving lower bounds on communication complexity. As a running example in this chapter, we will use the equality function: (cid:40) 1 if x = y EQ(x,y) = 0 otherwise It turns out that almost no improvement is possible over the trivial n+1 bit communication protocol for this function: 13.2. LOWER BOUND METHODS p13.3 (243) Theorem 13.4 (Equality has linear communication complexity) C(EQ) ≥ n We will prove Theorem 13.4 by several methods below. 13.2.1 The fooling set method ThefirstproofofTheorem13.4usesanideacalledfooling sets. Foranycommunicationprotocolfor any function, suppose x,x(cid:48) are any two different n-bit strings such that the communication pattern (i.e., sequence of bits transmitted) is the same on the input pairs (x,x) and (x(cid:48),x(cid:48)). Then we claim that the players’ final answer must be the same on all four input-pairs (x,x),(x,x(cid:48)),(x(cid:48),x),(x(cid:48),x(cid:48)). This is shown by an easy induction. If player 1 communicates a bit in the first round, then by hypothesis this bit is the same whether his input is x or x(cid:48). If player 2 communicates in the 2nd round, then his bit must also be the same on both inputs x and x(cid:48) since he receives the same bit from player 1. And so on. We conclude that at the end, the players’ answer on (x,x) must agree with their answer on (x,x(cid:48)). To show C(EQ) ≥ n it suffices to note that if a protocol exists whose complexity is at most n−1, then there are only 2n−1 possible communication patterns. But there are 2n choices for input pairs of the form (x,x) and so by the pigeonhole principle, there exist two distinct pairs (x,x) and (x(cid:48),x(cid:48)) on which the communication pattern is the same. But then the protocol must be incorrect, since EQ(x,x(cid:48)) = 0 (cid:54)= EQ(x,x). This completes the proof. This argument can be easily generalized as follows (Exercise 13.1): Lemma 13.5 Say that a function f : {0,1}n ×{0,1}n → {0,1} has a size M fooling set if there is an M-sized subset S ⊆ {0,1}n ×{0,1}n and a value b ∈ {0,1} such that (1) for every (cid:104)x,y(cid:105) ∈ S, f(x,y) = b and (2) for every distinct (cid:104)x,y(cid:105),(cid:104)x(cid:48),y(cid:48)(cid:105) ∈ S, either f(x,y(cid:48)) (cid:54)= b or f(x(cid:48),y) (cid:54)= b. If f has a size-M fooling set then C(f) ≥ logM. Example 13.6 (Disjointness) Let x,y be interpreted as characteristic vectors of subsets of {1,2,...,n}. Let DISJ(x,y) = 1 if these two subsets are disjoint, otherwise DISJ(x,y) = 0. As a corollary of Lemma 13.5 we obtain that C(DISJ) ≥ n since the following 2n pairs constitute a fooling set: (cid:8) (cid:9) S = (A,A) : A ⊆ {1,2,...,n} . 13.2.2 The tiling method The tiling method for lower bounds takes a more global view of the function f. Consider the matrix of f, denoted M(f), which is a 2n×2n matrix whose (x,y)’th entry is the value f(x,y) (see Figure 13.1.) We visualize the communication protocol in terms of this matrix. A combinatorial rectangle (or just rectangle for short) in the matrix M is a submatrix of M that corresponds to entries in A×B where A ⊆ {0,1}n, B ⊆ {0,1}n, we say that A×B is monochromatic if for all x in A and y in B, M is the same. If the protocol begins with the first player sending a bit, then x,y M(f) partitions into two rectangles of the type A ×{0,1}n, A ×{0,1}n, where A is the subset 0 1 b of the input for which the first player communicates the bit b. Notice, A ∪A = {0,1}n. If the 0 1 next bit is sent by the second player, then each of the two rectangles above is further partitioned into two smaller rectangles depending upon what this bit was. Finally, if the total number of bits p13.4 (244) 13.2. LOWER BOUND METHODS Player 2’s string 000 001 010 011 100 101 110 111 1 000 0 1 001 1 010 1 011 Player 1’s string 100 0 1 1 101 1 110 1 111 Figure 13.1: MatrixM(f)fortheequalityfunctionwhentheinputstotheplayershave3bits. Thenumbersinthe matrix are values of f. communicated is k then the matrix gets partitioned into 2k rectangles. Note that each rectangle in the partition corresponds to a subset of input pairs for which the communication pattern thus far has been identical. (See Figure 13.2 for an example.) When the protocol stops, the value of f is determined by the sequence of bits sent by the two players, and thus must be the same for all pairs x,y in that rectangle. Thus the set of all communication patterns must lead to a partition of the matrix into monochromatic rectangles. Player 2’s string 000 001 010 011 100 101 110 111 000 00 01 001 010 011 Player 1’s string 100 10 11 10 101 110 111 Figure 13.2: Two-way communication matrix after two steps. The large number labels are the concatenation of the bit sent by the first player with the bit sent by the second player. Definition 13.7 A monochromatic tiling of M(f) is a partition of M(f) into disjoint monochromatic rectangles. We denote by χ(f) the minimum number of rectangles in any monochromatic tiling of M(f). We have the following connection to communication complexity. Theorem 13.8 (Tiling and communication complexity [AhoUlYa83]) log χ(f) ≤ C(f) ≤ 16(log χ(f))2. 2 2 Proof: The first inequality follows from our above discussion, namely, if f has communication complexity k then it has a monochromatic tiling with at most 2k rectangles. The second inequality is left as Exercise 13.4. (cid:4) 13.2. LOWER BOUND METHODS p13.5 (245) Thefollowingobservationshowsthatforeveryfunctionf whosecommunicationcomplexitycan be lower bounded using the fooling set method, the communication complexity can also be lower bounded by the tiling method. Hence the latter method subsumes the former. Lemma 13.9 If f has a fooling set with m pairs, then χ(f) ≥ m. Proof: If (x ,y ) and (x ,y ) are two of the pairs in the fooling set, then they cannot be in a 1 1 2 2 monochromatic rectangle since not all of (x ,y ),(x ,y ), (x ,y ),(x ,y ) have the same f value. 1 1 2 2 1 2 2 1 (cid:4) 13.2.3 The rank method Now we introduce an algebraic method to lower bound χ(f) (and hence the communication com- plexity of f). Recall the notion of rank of a square matrix: the size of the largest subset of rows that are linearly independent. The following lemma (left as Exercise 13.5) gives an equivalent characterization of the rank: Lemma 13.10 The rank of an n×n matrix M over a field F, denoted by rank(M), is the minimum value of (cid:96) such that M can be expressed as (cid:96) (cid:88) M = B , i i=1 where each B is an n×n matrix of rank 1. i Note that 0,1 are elements of every field, so we can compute the rank of a binary matrix over any field we like. The choice of field can be crucial; see Exercise 13.8. Observing that every monochromatic rectangle can be viewed (by filling out entries outside the rectangle with 0’s) as a matrix of rank at most 1 , we obtain the following theorem: Theorem 13.11 For every function f, χ(f) ≥ rank(M(f)). Example 13.12 The matrix for the equality function is simply the identity matrix, and hence rank(M(Eq)) = 2n. Thus, C(EQ) ≥ logχ(EQ) ≥ n, yielding another proof of Theorem 13.4. 13.2.4 The discrepancy method For this method it is convenient to transform f into a ±1-valued function by using the map b (cid:55)→ (−1)b (i.e., 0 (cid:55)→ +1,1 (cid:55)→ −1. Thus M(f) will also be a ±1 matrix. We defined the discrepancy of a rectangle A×B in a 2n×2n matrix M to be (cid:12) (cid:12) (cid:12) (cid:12) 1 (cid:12) (cid:88) (cid:12) 22n (cid:12)(cid:12) Mx,y(cid:12)(cid:12) . (cid:12)x∈A,y∈B (cid:12) The discrepancy of the matrix M(f), denoted by Disc(f), is the maximum discrepancy among all rectangles. The following easy lemma relates it to χ(f). p13.6 (246) 13.2. LOWER BOUND METHODS 1 Lemma 13.13 χ(f) ≥ . Disc(f) Proof: If χ(f) ≤ K then there exists a monochromatic rectangle having at least 22n/K entries. Such a rectangle will have discrepancy at least 1/K. (cid:4) Lemma 13.13 can be very loose. For the equality function, the discrepancy is at least 1−2−n (namely, the discrepancy of the entire matrix), which would only give a lower bound of 2 for χ(f). However, χ(f) is at least 2n, as already noted. Now we describe a method to upper bound the discrepancy using eigenvalues. Lemma 13.14 (Eigenvalue bound) For any real matrix M, the discrepancy of a rectangle A×B is (cid:112) at most λ (M) |A||B|/22n, where λ (M) is the magnitude of the largest eigenvalue of M. max max Proof: Let 1 ∈ R2n denote the characteristic vectors of a subset S ⊆ {0,1}n (i.e., the xth S coordinate of 1 is equal to 1 if x ∈ S and to 0 otherwise). Note (cid:107)1 (cid:107) = (cid:112)(cid:80) 12 = (cid:112)|S|. Note S S 2 x∈S also that for every A,B ⊆ {0,1}n, (cid:80) M = 1† M1 . x∈A,y∈B x,y A B The discrepancy of the rectangle A×B is 1 1† M1 ≤ 1 λ (M)(cid:12)(cid:12)1† 1 (cid:12)(cid:12) ≤ 1 λ (M)(cid:112)|A||B|, 22n A B 22n max (cid:12) A B(cid:12) 22n max where the last inequality uses Cauchy-Schwartz. (cid:4) Example 13.15 (cid:80) Themod2innerproductfunctiondefinedasf(x,y) = x(cid:12)y = x y (mod2)hasbeenencountered i i i afewtimesinthisbook. Tobounditsdiscrepancy,letN bethepm1matrixcorrespondingtof (i.e., M = (−1)x(cid:12)y). It is easily checked that every two distinct rows (columns) of N are orthogonal, x,y every row has (cid:96) norm 2n/2, and that NT = N. Thus we conclude that N2 = 2nI where I is the 2 unit matrix. Hence every eigenvalue is either +2n/2 or −2n/2, and thus Lemma 13.14 implies that (cid:112) the discrepancy of a rectangle A×B is at most 2−3n/2 |A||B| and the overall discrepancy is at most 2−n/2 (since |A|,|B| ≤ 2n). 13.2.5 A technique for upper bounding the discrepancy We describe an upper bound technique for the discrepancy that will later be useful also in the multiparty setting (Section 13.3). As in Section 13.2.4, we assume that f is a ±1-valued function. We define the following quantity: Definition 13.16 (cid:104) (cid:105) (cid:81) (cid:81) E(f) = E f(a ,b ) . a1,a2,b1,b2 i=1,2 j=1,2 i j Note that E(f) can be computed, like the rank, in time polynomial in the size of the matrix M(f). By contrast, the definition of discrepancy involves a maximization over all possible subsets A,B, and a naive algorithm for computing it would take time exponential in the size of M(f). The following Lemma relates these two quantities. Lemma 13.17 Disc(f) ≤ E(f)1/4. 13.2. LOWER BOUND METHODS p13.7 (247) Proof: The proof follows in two steps. Claim 1: For every function h:{0,1}n×{0,1}n → {1,−1}, E(h) ≥ (E [f(a,b)])4. a,b We will use the Cauchy-Schwartz inequality, specifically, the version according to which E[z2] ≥ (E[z])2 for every random variable z.    (cid:89) (cid:89) E(h) = E  E  h(ai,bj) (1) a1,a2 b1,b2 i=1,2j=1,2 (cid:34) (cid:35) (cid:18) (cid:19)2 = E E[h(a ,b)h(a ,b)] (2) 1 2 a1,a2 b (cid:18) (cid:20) (cid:21)(cid:19)2 ≥ E E[h(a ,b)h(a ,b)] (Cauchy Schwartz) (3) 1 2 a1,a2 b (cid:18) (cid:19)4 ≥ E[h(a,b)] . (repeating previous two steps) (4) a,b Claim 2: For every function f there is a function h such that E(f) = E(h) and E [h(a,b)] ≥ a,b Disc(f). First, we note that for every two functions g ,g :{0,1}n → {−1,1}, if we define h = f ◦g ◦g 1 2 1 2 as h(a,b) = f(a,b)g (a)g (b) 1 2 then E(f) = E(h). The reason is that for all a ,a ,b ,b , 1 2 1 2 (cid:89) (cid:89) (cid:89) (cid:89) h(a ,b ) = g (a )2g (a )2g (b )2g (b )2 f(a ,b ) i j 1 1 1 2 2 1 2 2 i j i=1,2j=1,1 i=1,2j=1,2 and the square of any value of g ,g is 1. 1 2 Now we prove Claim 2 using the probabilistic method. Fix A,B ⊆ {0,1}n and define two random functions g ,g :{0,1}n → {−1,1} as below. First, for each a (cid:54)∈ A pick a random value 1 2 r in {−1,1} and for each b (cid:54)∈ B pick a random value s in {−1,1}. All random choices are a b independent of one another. Let (cid:40) 1 if a ∈ A g (a) = 1 r else a (cid:40) 1 if b ∈ B g (b) = 2 s else b Let h = f ◦g ◦g , and therefore E(h) = E(f). Furthermore 1 2 (cid:20) (cid:21) (cid:20) (cid:21) E E[h(a,b)] = E E [f(a,b)g (a)g (b)] (5) 1 2 g1,g2 a,b a,b g1,g2 1 (cid:88) = f(a,b) (6) 22n a∈A,b∈B = Disc(f) (7) where the second line follows from the fact that E [g (a)] = E [g (b)] = 0 for a (cid:54)∈ A and b (cid:54)∈ B. g1 1 g2 2 Thus in particular there exist g ,g such that |E [h(a,b)]| ≥ Disc(f). (cid:4) 1 2 a,b We will see an example for a lower bound using this technique in Section 13.3. p13.8 (248) 13.3. MULTIPARTY COMMUNICATION COMPLEXITY 13.2.6 Comparison of the lower bound methods The tiling argument is the strongest lower bound technique, since bounds on rank, discrepancy and fooling sets imply a bound on χ(f), and hence can never prove better lower bounds than the tiling argument. Also, as Theorem 13.10, logχ(f) fully characterizes the communication complexity of f up to a constant factor. The rank and fooling set methods are incomparable, meaning that each can be stronger than the other for some function. However, if we ignore constant factors, the rank method is always at least as strong as the fooling set method (see Exercise 13.6). Also, we can separate the power of these lower bound arguments. For instance, we know functions for which a polynomial gap exists between logχ(f) and logrank(M(f)). However, the following conjecture (we only state one form of it) says that rank is in fact optimal up to a polynomial factor. Conjecture 13.18 (log rank conjecture) There is a constant c > 1 such that C(f) = O(log(rank(M(f)))c) for all f and all input sizes n, where rank is taken over the reals. Of course, the difficult part of the above conjecture is to show that low rank implies a low- complexity protocol for f. Though we are still far from proving this, Nisan and Wigderson have shown that at least low rank implies low value of 1/Disc(f). Theorem 13.19 ([NisanWi95]) 1/Disc(f) = O(rank(f)3/2). 13.3 Multiparty communication complexity There is more than one way to generalize communication complexity to a multiplayer setting. The most interesting model turns out to be the “number on the forehead” model: each player has a string on his head which everybody else can see but he cannot. That is, there are k players and k strings x ,...,x , and Player i gets all the strings except for x . The players are interested 1 k i in computing a value f(x ,x ,...,x ) where f : ({0,1}n)k → {0,1} is some fixed function. As 1 2 k in the 2-player case, the k players have an agreed-upon protocol for communication (which was decided before they were given their strings), and all their communication is posted on a “public blackboard” that all of them can see (the protocol also determines the order in which the players write on the blackboard). The last message sent should contain (or at least easily determine) the value f(x ,...,x ) of the function on the inputs. By analogy with the 2-player case, we denote by 1 k C (f) the number of bits that must be exchanged by the best protocol. Note that it is at most k n+1, since it suffices for any j (cid:54)= i to write x on the blackboard, at which point the ith player i knows all k strings and can determine and publish f(x ,...,x ). 1 k Example 13.20 Consider computing the function n (cid:77) f(x ,x ,x ) = maj(x ,x ,x ) 1 2 3 1i 2i 3i i=1 in the 3-party model where x ,x ,x are n bit strings. The communication complexity of this 1 2 3 function is 3: each player counts the number of i’s such that she can determine the majority of x ,x ,x by examining the bits available to her. She writes the parity of this number on the 1i 2i 3i blackboard, and the final answer is the parity of the players’ bits. This protocol is correct because the majority for each row is known by either 1 or 3 players, and both are odd numbers.