Prof. Mark Bun
CAS CS 591 B: Communication Complexity
Lecture Notes 2: Fooling Sets, Rank, and Covers
Fall 2019
Reading.
• Rao-Yehudayoff Chapter 1 (Fooling Sets and Rectangle Covers), Chapter 2 (through pg. 58) 1 Fooling Sets
The method of fooling sets refines arguments based on rectangle size. Intuitively, a fooling set is a set of inputs which is hard to cover by disjoint unions of rectangles. Formally, a fooling set for a function f is a set S ⊆ X × Y such that |R ∩ S| ≤ 1 for every rectangle R which is monochromatic with respect to f.
Theorem 1 If S is a fooling set for f, then Pcc(f) ≥ log |S|.
Proof: Recall that any protocol computing f with c bits of communication partitions X × Y into at most 2c monochromatic rectangles. Any partition of X × Y into monochromatic rectangles must be at least as large as S. Hence |S| ≥ 2Pcc(f).
Example 2 Going back to EQn, we can take S = {(x,x) : x ∈ {0,1}n} to see that Pcc(EQn) ≥ n.
Example 3 Consider the function GTn. We claim that the set S = {(x,x) : x ∈ {0,1}n} is a fooling set for GTn. To see this, suppose T is a monochromatic set which contains both (x,x) and (x′, x′), and suppose WLOG that x < x′. Then T cannot contain (x, x′) so it is not a rectangle.
Example 4 One of the central functions in the study of communication complexity is the disjoint- ness function DISJn : {0, 1}n × {0, 1}n → {0, 1}. This function is defined by DISJn(x, y) = 1 iff for every index i, either xi = 0 or yi = 0. Equivalently, this function checks whether the sets for which x and y are indicator vectors are disjoint.
We can prove a lower bound of n on Pcc(DISJn) using the fooling set S = {(x, x ̄) : x ∈ {0, 1}n}. Note that DISJn(x, x ̄) = 1 for every pair of inputs in S. To see that this is a fooling set, let T be a monochromatic set containing both (x, x ̄) and (x′, x ̄′). Then either (x, x ̄′) or (x′, x ̄) must intersect, so T cannot be a rectangle.
2 Rank
A two-party communication problem f : X × Y → {0, 1} naturally corresponds to a matrix Mf as follows. The rows of Mf are indexed by elements of X and the columns are indexed by elements of Y and Mf[x,y] = f(x,y). Let rank(f) = rank(Mf).
To understand the connection between rank and deterministic communication, we need two facts. The first is that combinatorial rectangles have low rank.
1
Lemma 5 Let A × B ⊂ X × Y be a non-empty combinatorial rectangle. Then the matrix M where M[x,y]=1 if (x,y)∈A×B and M[x,y]=0 otherwise has rank 1.
Proof: Let vA ∈ {0, 1}|X| and vB ∈ {0, 1}|Y | be the indicator vectors for A and B, respectively. Then M = vAvBT , and hence M has rank 1.
The second is that rank is subadditive.
Fact 6 Let M and N be matrices with the same dimensions. Then rank(M + N) ≤ rank(M) + rank(N ).
Proof: Let CM and CN denote the sets of columns of M and N, respectively, so rank(M) = dim span(CM ) and rank(N ) = dim span(CN ). The column span of M + N is contained in the span(CM ∪CN),sorank(M+N)≤dimspan(CM ∪CN)≤rank(M)+rank(N).
Theorem7 Foranyfunctionf:X×Y →{0,1},wehavePcc(f)≥logrank(f).
Proof: Let Π be a protocol computing f with cost c. For each leaf l of Π on which the protocol outputs 1, let Ml be the matrix with Rl[x,y] = 1 if (x,y) reaches l and Rl[x,y] = 0 otherwise. Since Ml is the indicator of a rectangle, rank(Ml) = 1. Moreover, Mf = l Ml, so rank(Mf ) ≤ l rank(Ml) ≤ 2c. Hence c ≥ log rank(f).
Example 8 The equality and greater-than functions correspond to matrices of full rank 2n, and hence have deterministic communication complexity ≥ n.
2.1 The Log Rank Conjecture
Deterministic communication can also be upper bounded by rank itself. To see this, suppose Mf has rank r. Then we can decompose Mf = A·B where A is an |X|×r Boolean matrix and Y is a r × |Y | real matrix. Observe that f(x, y) = eTx Mf ey = eTx ABey, where ex and ey are the indicators for x and y respectively. So Alice can send Bob the r-dimensional Boolean vector eTx A which suffices for him to compute f(x,y).
There’s an exponential gap between the best known bounds on Pcc in terms of rank: log rank(f ) ≤ Pcc(f) ≤ O ̃(rank(f)). (The improved upper bound was obtained by Lovett in 2013.) Which bound is closer to the truth? Thirty years ago, Lovász and Saks conjectured that the lower bound is tight up to polynomial factors, namely that that there is a constant c ≥ 1 such that logrank(f) ≤ Pcc(f) ≤ O(logc rank(f)). This is probably the most famous conjecture in commu- nication complexity.
While we are far from resolving the log rank conjecture itself, we do know a lot about related formulations in other models. For instance, the log of the sign-rank of a matrix characterizes its UPPcc complexity up to an additive constant. On the other hand, a recent breakthrough of Chattopadhyay, Mande, and Sherif showed an exponential gap between the log of the approximate- rank of a matrix and its BPPcc complexity, refuting the “approximate log rank conjecture.” More on these later in the course.
2
3 Covers and Nondeterminism
Recall that we can lower bound deterministic communication by showing that we need many monochromatic rectangles to partition the input space. A stronger statement (which could per- haps be easier to prove in practice for specific functions) is to show that we need many rectangles just to cover the 0-inputs or the 1-inputs to a function. More precisely let us define the 0-cover and 1-cover numbers as follows.
Definition 9 For b ∈ {0,1}, let Cb(f) be the minimum number of rectangles needed to cover the b-inputs to f. Namely, it is the smallest set of rectangles whose union equals f−1(b).
Clearly log C0(f) and log C1(f) are both lower bounds on Pcc(f).
Example 10 Let’s look at the covering numbers for the Equality function. Recall that we used the fooling set method to show that C1(EQn) ≥ 2n. On the other hand, C0(EQn) ≤ 2n. To see this, consider the set of rectangles of the form Ri,b = {(x, y) : xi = b, yi ̸= b}.
The above example points out an interesting property of the Equality function: It has low co- nondeterministic complexity. Namely, on an pair of inputs (x,y) for which EQn(x,y) = 0, and a proof of length only logn capturing the index i on which xi ̸= yi, Alice and Bob can verify that x ̸= y using only 2 bits of communication. On the other hand, the nondeterministic complexity of EQ is still high, as it is hard for Alice and Bob to verify that x = y even with an O(n)-length proof.
This motivates us to study nondeterministic and co-nondeterministic protocols.
Definition 11 A nondeterministic protocol is a collection of deterministic protocols {Πw : w ∈ {0,1}s}. Such a protocol computes a function f if
• For every (x,y) ∈ f−1(1) there exists a w ∈ {0,1}s such that Πw(x,y) = 1
• For every (x,y) ∈ f−1(0), for all w ∈ {0,1}s we have Πw(x,y) = 0.
The cost of such a protocol is s + maxw∈{0,1}s cost(Πw), and the nondeterministic communication complexity of a function f, denoted NPcc(f), is the least cost of such a protocol computing f. Simi- larly, a co-nondeterministic protocol computes f if 1) for every (x,y) ∈ f−1(1), we have Πw(x,y) = 1 for all w ∈ W and 2) for every (x,y) ∈ f−1(0) there exists w ∈ W such that Πw(x,y) = 0. The co-nondeterministic communication complexity of f is denoted by coNPcc(f).
Nondeterministic communication complexity is tightly characterized by covering numbers.
Theorem 12 For every function f : X ×Y → {0,1}, we have NPcc(f) = logC1(f)+Θ(1) and coNPcc(f) = log C0(f) + Θ(1).
Proof: We prove this for NPcc. First, suppose f admits a nondeterministic protocol with witness size s and protocol length c. Then the 1-inputs to f are covered by a union of 2s ·2c 1-monochromatic rectangles. Hence C1(f) ≤ 2NPcc(f).
Now we show how to design a nondeterministic protocol for f which has a small covering number. Let {Rw} be a cover of the 1-inputs of f. Then f(x,y) = 1 iff there exists a w such that (x,y) ∈ Rw. So given w as a proof, Alice and Bob can verify whether (x, y) ∈ Rw using 2 bits of communication, and hence NPcc(f) ≤ ⌈log C1(f)⌉ + 2.
3
Theorem 13 For every function f, we have Pcc(f) ≤ O(log C0(f) · log C1(f)) ≤ O(NPcc(f) · coNPcc (f )).
Proof: We sketch an “algorithmic” proof of this result which is reminiscent of the protocol for Clique vs. Independent Set. Given a small 0-cover and a small 1-cover, we will design a protocol which uses binary search to try to find a 0-rectangle containing (x,y), thus proving that f(x,y) = 0. (If the protocol fails, then we can conclude that f(x, y) = 1.) In each of stages i = 1, . . . , log C0(f), let Ti be the set of “live” 0-rectangles which could still contain (x,y). In every round, Alice and Bob will transmit O(logC1(f)) bits to decrease the size of Ti by a factor of 2, giving a total of O(log C0(f) · log C1(f)) bits of communication.
The way to do this pruning is as follows. If there is a 1-rectangle containing row x whose row set intersects at most half of the rows sets of the rectangles in Ti, then Alice can send its identity to Bob with O(logC1(f)) bits and the parties can remove the remaining half of Ti from consideration. Otherwise, if there is a 1-rectangle containing column y that intersects at most half of Ti in columns, Bob can send its identity to Alice. Note that a 0-rectangle containing x will always survive this pruning process. If neither Alice nor Bob can find such a 1-rectangle, then the parties can conclude that f (x, y) = 0. To see this, suppose instead that (x, y) were contained in a 1-rectangle R. Then by the pigeonhole principle, R could intersect at most half of Ti in rows and at most half of Ti in columns, so Alice or Bob would be able to prune.
Theorem 13 tells us that if f has both a good nondeterministic protocol and a good co- nondeterministic protocol, then it has a good deterministic protocol. One way to state this suc- cinctly is as follows. By abusing notation, define the complexity classes Pcc , NPcc , coNPcc as the sequences of functions {fn : {0, 1}n × {0, 1}n → {0, 1}} which have (log n)O(1)-cost determin- istic, nondeterministic, and co-nondeterministic protocols, respectively. Then Theorem 13 implies Pcc = NPcc ∩ coNPcc. Also note that Example 10 shows that Pcc coNPcc, and by comple- menting, Pcc NPcc.
4