Lower Bounds in Communication Complexity: A Survey
Troy Lee Adi Shraibman Columbia University Weizmann Institute
Abstract
We survey lower bounds in communication complexity. Our focus is on lower bounds that work by first representing the communication complexity measure in Euclidean space. That is to say, the first step in these lower bound techniques is to find a geometric complexity measure such as rank, or the trace norm that serves as a lower bound to the underlying communication complexity measure. Lower bounds on this geometric complexity measure are then found using algebraic and geometric tools.
Contents
1 Introduction 4
2 Deterministic communication complexity 14
2.1 Logrankconjecture ………………….. 18
2.2 Nonnegativerank……………………. 19
2.3 Normbasedmethods………………….. 20
2.3.1 Tracenorm …………………… 21 2.3.2 γ2norm…………………….. 23 2.3.3 μnorm …………………….. 25 2.3.4 Thenuclearnorm………………… 26 2.3.5 Dualnorms …………………… 27
2.4 Summary ……………………….. 29
3 Nondeterministic communication complexity 31
3.1 Relation between deterministic and nondeterministic complexity 33
3.2 Relationwithnonnegativerank…………….. 35
3.3 Fractionalcover…………………….. 35
3.4 Summary ……………………….. 38
4 Randomized communication complexity 39
4.1 Approximaterank …………………… 42 4.2 Approximatenorms ………………….. 44 4.3 DiagonalFouriercoefficients………………. 48 4.4 Distributional complexity and discrepancy . . . . . . . . . . . 51 4.5 Corruptionbound …………………… 53 4.6 Summary ……………………….. 56
5 Quantum communication complexity 58
5.1 Definitionofthemodel…………………. 58 5.2 Approximaterank …………………… 60
2
5.3 Alowerboundviaγ2α …………………. 61 5.3.1 XORgames…………………… 62
5.3.2 A communication protocol gives a XOR protocol . 5.4 Summary: equivalentrepresentations . . . . . . . . . . . .
6 The role of duality in proving lower bounds
. . 64 . . 65
67
. . 67
6.1 Dualityandtheseparationtheorem. . . . . . . . . . . . . 6.1.1 Dual space, dual norms and the duality transform
.. 68 6.2 Applying the separation theorem – finding a dual formulation 71 6.2.1 Distributionalcomplexity ……………. 71 6.2.2 Approximatenorms ………………. 73
7 Choosing a witness 75
7.1 Nonnegativeweighting…………………. 75
7.2 Blockcomposedfunctions ……………….. 79 7.2.1 Stronglybalancedinnerfunction . . . . . . . . . . . . 83 7.2.2 TriangleInequality……………….. 87 7.2.3 Examples ……………………. 89 7.2.4 XORfunctions …………………. 91
8 Multiparty communication complexity 95
8.1 Protocoldecomposition ………………… 96
8.2 Bounding number-on-the-forehead discrepancy . . . . . . . . 98 8.2.1 Example:Hadamardtensors ………….. 99
8.3 PatternTensors……………………..100
8.4 Applications……………………….105
8.4.1 Thecomplexityofdisjointness. . . . . . . . . . . . . . 105
8.4.2 Separating communication complexity classes . . . . . 107
9 Upper bounds on multiparty communication complexity 109
9.1 Streaminglowerbounds …………………110
9.2 NOFupperbounds……………………112 9.2.1 ProtocolofGrolmusz……………….113 9.2.2 Protocolforsmallcircuits…………….114
3
Chapter 1
Introduction
Communication complexity studies how much communication is needed in order to evaluate a function whose output depends on information dis- tributed amongst two or more parties. Yao [Yao79] introduced an elegant mathematical framework for the study of communication complexity, ap- plicable in numerous situations, from an email conversation between two people, to processors communicating on a chip. Indeed, the applicability of communication complexity to other areas, including circuit and formula complexity, VLSI design, proof complexity, and streaming algorithms, is one reason why it has attracted so much study. See the excellent book of Kushilevitz and Nisan [KN97] for more details on these applications and communication complexity in general.
Another reason why communication complexity is a popular model for study is simply that it is an interesting mathematical model. Moreover, it has that rare combination in complexity theory of a model for which we can actually hope to show tight lower bounds, yet these bounds often require the development of nontrivial techniques and sometimes are only obtained after several years of sustained effort.
In the basic setting of communication complexity, two players Alice and Bobwishtocomputeafunctionf :X×Y →{T,F}whereX,Y arearbitrary finite sets. Alice holds an input x ∈ X, Bob y ∈ Y , and they wish to evaluate f (x, y) while minimizing the number of bits communicated. We let Alice and Bob have arbitrary computational power as we are really interested in how much information must be exchanged in order to compute the function, not issues of running time or space complexity.
Formally, a communication protocol is a binary tree where each internal node v is labeled either by a function av : X → {0,1} or a function bv :
4
Y → {0, 1}. Intuitively each node corresponds to a turn of either Alice or Bob to speak. The function av indicates, for every possible input x, how Alice will speak if the communication arrives at that node, and similarly for bv. The leaves are labeled by an element from {T,F}. On input x,y the computation traces a path through the tree as indicated by the functions av,bv. The computation proceeds to the left child of a node v if av(x) = 0 and the right child if av(x) = 1, and similarly when the node is labeled by bv. The protocol correctly computes f if for every input x,y, the computation arrives at a leaf l labeled by f(x,y).
The cost of a protocol is the height of the protocol tree. The deter- ministic communication complexity of a function f, denoted D(f), is the minimum cost of a protocol correctly computing f. Notice that, as we have defined things, the transcript of the communication defines the output, thus both parties “know” the answer at the end of the protocol. One could alter- natively define a correct protocol where only one party needs to know the answer at the end, but this would only make a difference of one bit in the communication complexity.
If we let n = min{⌈log|X|⌉,⌈log|Y|⌉} then clearly D(f) ≤ n+1 as either Alice or Bob can simply send their entire input to the other, who can then compute the function and send the answer back. We refer to this as the trivial protocol. Thus the communication complexity of f will be a natural number between 1 and n + 1, and our goal is to determine this number. This can be done by showing a lower bound on how much communication is needed, and giving a protocol of matching complexity.
The main focus of this survey is on showing lower bounds on the com- munication complexity of explicit functions. We treat different variants of communication complexity, including randomized, quantum, and multiparty models. Many tools have been developed for this purpose from a diverse set of fields including linear algebra, Fourier analysis, and information theory. As is often the case in complexity theory, demonstrating a lower bound is usually the more difficult task.
One of the most important lower bound techniques in communication complexity is based on matrix rank. In fact, it is not too much of an exag- geration to say that a large part of communication complexity is the study of different variants of matrix rank. To explain the rank bound, we must first introduce the communication matrix, a very useful and common way of representing a function f : X × Y → {T,F}. We will consider both a Boolean and a sign version of the communication matrix, the difference being in the particular integer representation of {T,F}. A Boolean matrix has all entries from {0, 1}, whereas a sign matrix has entries from {−1, +1}. The
5
Boolean communication matrix for f, denoted Bf , is a |X|-by-|Y | matrix where Bf[x,y] = 1 if f(x,y) = T and Bf[x,y] = 0 if f(x,y) = F. The sign communication matrix for f , denoted Af , is a {−1, +1}-valued matrix where Af[x,y] = −1 if f(x,y) = T and Af[x,y] = +1 if f(x,y) = F. Depending on the particular situation, it can be more convenient to reason about one repre- sentation or the other, and we will use both versions throughout this survey. Fortunately, this choice is usually simply a matter of convenience and not of great consequence—it can be seen that they are related as Bf = (J − Af )/2, where J is the all-ones matrix. Thus the matrix rank of the two versions, for example, will differ by at most one.
Throughout this survey we identify a function f : X × Y → {T , F } with its corresponding (sign or Boolean) communication matrix. The represen- tation of a function as a matrix immediately puts tools from linear algebra at our disposal. Indeed, Mehlhorn and Schmidt [MS82] showed how matrix rank can be used to lower bound deterministic communication complexity. This lower bound follows quite simply from the properties of a deterministic protocol, but we delay a proof until Chapter 2.
Theorem 1 (Mehlhorn and Schmidt [MS82]) For every sign matrix A, log rank(A) ≤ D(A).
The rank bound has nearly everything one could hope for in a lower bound technique. From a complexity point of view it can be efficiently computed, i.e. computed in time polynomial in the size of the matrix. Fur- thermore, it frees us from thinking about communication protocols and lets us just consider the properties of A as a linear operator between Euclidean spaces, with all the attendant tools of linear algebra to help in doing this. Finally, it is even conjectured that one can always show polynomially tight bounds via the rank method. This log rank conjecture is one of the greatest open problems in communication complexity.
Conjecture 2 (Lovász and Saks [LS88]) There is a constant c such that for every sign matrix A
D(A) ≤ (log rank(A))c + 2.
The additive term is needed because a rank-one sign matrix can require two bits of communication. Thus far the largest known separation between log rank and deterministic communication, due to Nisan and Wigderson [NW95], shows that in Conjecture 2 the constant c must be at least 1.63 . . .
6
The problems begin, however, when we start to study other models of communication complexity such as randomized, quantum, or multiparty vari- ants. Here one can still give a lower bound in terms of an appropriate vari- ation of rank, but the bounds now can become very difficult to evaluate. In the case of multiparty complexity, for example, the communication matrix becomes a communication tensor, and one must study tensor rank. Unlike matrix rank, the problem of computing tensor rank is NP-hard [Hås90], and even basic questions like the largest possible rank of an n-by-n-by-n real tensor remain open.
For randomized or quantum variants of communication complexity, as shown by Krause [Kra96] and Buhrman and de Wolf [BW01] respectively, the relevant rank bound turns out to be approximate rank.
Definition 3 Let A be a sign matrix. The approximate rank of A with approximation factor α, denoted rankα(A), is
rankα(A) = min rank(B). B:1≤A[i,j]B[i,j]≤α
As we shall see in Chapter 4 and Chapter 5, the logarithm of approx- imate rank is a lower bound on randomized and quantum communication complexity, where the approximation factor α relates to the success prob- ability of the protocol. In analogy with the log rank conjecture, it is also reasonable to conjecture here that this bound is polynomially tight.
Approximate rank, however, can be quite difficult to compute. While we do not know if it is NP-hard, similar rank minimization problems subject to linear constraints are NP-hard, see for example section 7.3 of [VB96]. Part of this difficulty stems from the fact that approximate rank is an optimization problem over a nonconvex function.
This brings us to the main theme of our survey. We focus on lower bound techniques which are real-valued functions and ideally possess some “nice” properties, such as being convex. The development and application of these techniques follows a three-step approach which we now describe. This approach can be applied in much the same way for different models, be they randomized, quantum, or multiparty.
Say that we are interested in a complexity measure CC, a mapping from functions to the natural numbers, which could represent any one of the above models.
1. Embed the problem in Rm×n. That is, find a function G : Rm×n → R such that
G(A) ≤ CC(A), 7
for every sign matrix A. As is the case with rank and approximate rank, often G will itself be naturally phrased as a minimization problem.
2. Find an equivalent formulation of G in terms of a maximization prob- lem. This will of course not always be possible, as in the case of ap- proximate rank. This can be done, however, for rank and for a broad class of optimization problems over convex functions.
3. Prove lower bounds on G by exhibiting an element of the feasible set for which the objective function is large. We call such an element a witness as it witnesses that G is at least as large as a certain value.
We will delay most of the technical details of this approach to the main body of the survey, in particular to Chapter 6 where we discuss the use of duality to perform the key step 2 to go from a “min” formulation to a “max” formulation. Here we limit ourselves to more general comments, providing some intuition as to why and in what circumstances this approach is useful.
Step 1 We are all familiar with the idea that it can be easier to find the extrema of a smooth real-valued function than a discrete valued function. For example, for smooth functions the powerful tools of calculus are available. To illustrate, think of integer programming vs. linear programming. The latter problem can be solved in polynomial time, while even simple instances of integer programming are known to be NP-hard.
The intuition behind the first step is the same. The complexity of a proto- col is a discrete valued function, so in determining communication complexity we are faced with an optimization problem over a discrete valued function. By working instead with a real valued lower bound G we will have more tools at our disposal to evaluate G. Moreover, if G is “nice”—for example being an optimization problem over a convex function—then the set of tools available to us is particularly rich. For instance, we can use duality to enact step 2.
We do potentially pay a price in performing Step 1 and working with a “nicer” function G. It could be the case that G(A) is much smaller than CC(A) for some sign matrices A. Just as in approximation algorithms, we seek a bound that is not only easier to compute but also approximates CC(A) well. We will say that a representation G(A) is faithful if there is some constant k such that CC(A) ≤ G(A)k for all sign matrices A.
Step 2 A communication complexity measure CC(A) is naturally phrased as a minimization problem—looking for a protocol of minimum cost. Often
8
times, as with the case of approximate rank, our lower bound G is also naturally phrased as a minimization problem.
The difficulty, of course, is that to lower bound a minimization problem one has to deal with the universal quantifier ∀—we have to show that every possible protocol requires a certain amount of communication.
When our complexity measure G is of a nice form, however, such as a minimization problem of a convex function, we can hope to find an equiva- lent formulation of G in terms of a maximization problem. A maximization problem is much easier to lower bound since we simply have to demonstrate a particular feasible instance for which the target function is large. In some sense this can be thought of as an “algorithmic approach” to lower bounds. In Chapter 6 we will show how this can be done for a large class of complexity measures known as approximate norms.
This is an instance of a more general phenomena: showing a statement about existence is often easier than proving a statement about nonexistence. The former can be certified by a witness, which we do not always expect for the latter. Take the example of graph planarity, i.e. the question of whether a graph can be drawn in the plane in such a way that its edges intersect only at their endpoints. While it can be tricky to find such a drawing, at least we know what form the answer will take. To show that a graph is nonplanar, however, seems like a much more daunting task unless one has heard of Kuratowski’s Theorem or Wagner’s Theorem. These theorems reduce the problem of nonexistence to that of existence: for example, Wagner’s theorem states that a graph is nonplanar if and only if it contains K5, the complete graph on five vertices, or K3,3 the complete three-by-three bipartite graph, as a minor. Not surprisingly, theorems of this flavor are key in efficient algorithmic solutions to planarity and nonplanarity testing.
Step 3 Now that we have our complexity measure G phrased in terms of a maximization problem, we are in much better shape. Any element from the feasible set can be used to show a lower bound, albeit not necessarily a good one. As a simple example, going back to the rank lower bound, observe that a natural way to prove a lower bound on rank is to find a large set of columns (or rows) that are independent.
Finding a good witness to prove a lower bound for a certain complexity measure G can still be a very difficult task. This is the subject we take up in Chapter 7. There are still only a few situations where we know how to choose a good witness, but this topic has recently seen a lot of exciting progress and more is certainly still waiting to be discovered.
9
Approximate norms The main example of the three-step approach we study in this survey is for approximate norms. We now give a more technical description of this case; the reader can skip this section at first reading, or simply take it as an “impression” of what is to come.
LetΦbeanynormonRm×n,andletα≥1bearealnumber. The α-approximate norm of an m × n sign matrix A is
Φα(A) = min Φ(B). B:1≤A[i,j]B[i,j]≤α
The limit as α → ∞ motivates the definition Φ∞(A) = min Φ(B).
B:1≤A[i,j]B[i,j]
In Step 1 of the framework described above we will usually take G(A) = Φα(A) for an appropriate norm Φ. We will see that the familiar matrix trace norm is very useful for showing communication complexity lower bounds, and develop some more exotic norms as well. We discuss this step in each of the model specific chapters, showing which norms can be used to give lower bounds on deterministic (Chapter 2), nondeterministic (Chapter 3), randomized (Chapter 4), quantum (Chapter 5), and multiparty (Chapter 8) models.
The nice thing about taking G to be an approximate norm is that we can implement Step 2 of this framework in a general way. As described in Chapter 6, duality can be applied to yield an equivalent formulation for any approximate norm Φα in terms of a maximization. Namely, for a sign matrix A
Φα(A) = max (1 + α)⟨A, W ⟩ + (1 − α)∥W ∥1 W 2Φ∗(W)
Here Φ∗ is the dual norm:
Φ∗(W) = max ⟨W,X⟩ X Φ(X)
We have progressed to Step 3. We need to find a witness matrix W that makes the bound from Equation (1.1) large. As any matrix W at all gives a lower bound, we can start with an educated guess and modify it according to the difficulties that arise. This is similar to the case discussed earlier of trying to prove that a graph is planar—one can simply start drawing and see how it goes. The first choice of a witness that comes to mind is the target matrix A itself. This gives the lower bound
Φα(A)≥ (1+α)⟨A,A⟩+(1−α)∥A∥1 = mn . (1.2) 2Φ∗ (A) Φ∗ (A)
10
(1.1)
This is actually not such a bad guess; for many interesting norms this lower bound is tight with high probability for a random matrix. But it is not always a good witness, and there can be a very large gap between the two sides of the inequality (1.2). One reason that the matrix A might be a bad witness, for example, is that it contains a large submatrix S for which Φ∗(S) is relatively large.
A way to fix this deficiency is to take instead of A any matrix P ◦ A, where P is a real matrix with nonnegative entries that sum up to 1. Here ◦ denotes the entry-wise product. This yields a better lower bound
Φα(A)≥ max 1 P:P≥0 Φ∗(P◦A)
∥P∥1=1
. (1.3)
Now, by a clever choice of P, we can for example give more weight to a good submatrix of A and less or zero weight to submatrices that attain large values on the dual norm. Although this new lower bound is indeed better, it is still possible to exhibit an exponential gap between the two sides of (1.3). This is nicely explained by the following characterization given in Chapter 7.
Theorem 4 For every sign matrix A
Φ∞(A)= max 1 P:P≥0 Φ∗(P◦A)
∥P∥1=1
.
The best value a witness matrix W which has the same sign as A in each entry can provide, therefore, is equal to Φ∞(A). It can be expected that there are matrices A for which Φ∞(A) is significantly smaller than Φα(A) for say α = 2 1. This is indeed the case for some interesting communica- tion complexity problems such as the SET INTERSECTION problem where f(x,y) = i(xi∧yi), which will be a running example throughout the survey.
When Φ∞(A) is not a good lower bound on Φα(A) for bounded α, there are only a few situations where we know how to choose a good witness. One case is where A is the sign matrix of a so-called block composed function, that is, a function of the form (f • gn)(x, y) = f(g(x1, y1), . . . , g(xn, yn)) where x = (x1,…,xn) and y = (y1,…,yn). This case has recently seen exciting progress [She09, She08c, SZ09b]. These works showed a lower bound on the complexity of a block composed function in terms of the approximate degree of f, subject to the inner function g satisfying some technical conditions. The
1Notice that Φα(A) is a decreasing function of α. 11
strength of this approach is that the approximate degree of f : {0, 1}n → {−1, +1} is often easier to understand than its communication complexity. In particular, in the case where f is symmetric, i.e. only depends on the Hamming weight of the input, the approximate polynomial degree has been completely characterized [Pat92]. These results are described in detail in Chapter 7.2.
Historical context The “three-step approach” to proving communication complexity lower bounds has already been used in the first papers studying communication complexity. In 1983, Yao [Yao83] gave an equivalent “max” formulation of randomized communication complexity using von Neumann’s minimax theorem. He showed that the 1/3-error randomized communication complexity is equal to the maximum over all probability distributions P , of the minimum cost of a deterministic protocol which errs with probability at most 1/3 with respect to P . Thus one can show lower bounds on randomized communication complexity by exhibiting a probability distribution which is hard for deterministic protocols. This principle is the starting point for many lower bound results on randomized complexity.
A second notable result using the “three-step approach” is a character- ization by Karchmer, Kushilevitz, and Nisan [KKN95] of nondeterministic communication complexity. Using results from approximation theory, they show that a certain linear program characterizes nondeterministic commu- nication complexity, up to small factors. By then looking at the dual of this program, they obtain a “max” quantity which can always show near optimal lower bounds on nondeterministic communication complexity.
The study of quantum communication complexity has greatly contributed to our understanding of the role of convexity in communication complexity lower bounds, and these more recent developments occupy a large portion of this survey. The above two examples are remarkable in that they im- plement the “three-step approach” with a (near) exact representation of the communication model. For quantum communication complexity, however, we do not yet have such a characterization which is convenient for showing lower bounds. The search for good representations to approximate quantum communication complexity led in particular to the development of approx- imate norms [Kla01, Raz03, LS09c]. Klauck (Lemma 3.1) introduced what we refer to in this survey as the μα approximate norm, also known as the generalized discrepancy method. While implicit in Klauck and Razborov, the use of Steps 2 and 3 of the three-step approach becomes explicit in later works [LS09c, She08c, SZ09b].
12
What is not covered In the thirty years since its inception, communica- tion complexity has become a vital area of theoretical computer science, and there are many topics which we will not have the opportunity to address in this survey. We mention some of these here.
Much work has been done on protocols of a restricted form, for example one-way communication complexity where information only flows from Alice to Bob, or simultaneous message passing where Alice and Bob send a message to a referee who then outputs the function value. A nice introduction to some of these results can be found in [KN97]. In this survey we focus only on general protocols.
For the most part, we stick to lower bound methods that fit into the gen- eral framework described earlier. As we shall see, these methods do encom- pass many techniques proposed in the literature, but not all. In particular, a very nice approach which we do not discuss are lower bounds based on information theory. These methods, for example, can give an elegant proof of the optimal Ω(n) lower bound on the SET INTERSECTION problem. We refer the reader to [BYJKS04] for more details.
We also restrict ourselves to the case where Alice and Bob want to com- pute a Boolean function. The study of the communication complexity of rela- tions is very interesting and has nice connections to circuit depth and formula size lower bounds. More details on this topic can be found in Kushilevitz and Nisan [KN97].
Finally, there are some models of communication complexity which we do not discuss. Perhaps the most notable of these is the model of unbounded- error communication complexity. This is a randomized model where Alice and Bob only have to succeed on every input with probability strictly greater than 1/2. We refer the reader to [For02, She08d, RS08] for interesting recent developments on this model.
13
Chapter 2
Deterministic communication complexity
In this chapter, we look at the simplest variant of communication complexity, where the two parties act deterministically and are not allowed to err. As we shall see, many of the lower bound techniques we develop for this model can be fairly naturally extended to more powerful models later on.
Say that Alice and Bob wish to arrange a meeting, and want to know if there is a common free slot in their busy schedules. How much might Alice and Bob have to communicate to figure this out? We will shortly see that, in the worst case, Alice may have to send her entire agenda to Bob.
We can describe this scenario as a function f : {0,1}n×{0,1}n → {T,F} where the ones in Alice and Bob’s input represent the free time slots. This function is one of the recurrent examples of our survey, the SET INTER- SECTION function. In general, the two binary inputs x,y ∈ {0,1}n are thought of as characteristic vectors of subsets of [n] = {1 . . . n}. Alice and Bob wish to decide whether these subsets intersect.
We informally described a deterministic protocol in the introduction; let us now make this formal.
Definition 5 A deterministic protocol for a function f : X × Y → {T , F } is a binary tree T with internal nodes labeled either by a function av : X → {0,1} or bv : Y → {0,1}, and leaves labeled by elements from {T,F}. An input (x,y) defines a path in T from the root to a leaf as follows: beginning at the root, at an internal node v move to the left child of v if av(x) = 0 or bv(y) = 0 and otherwise move to the right child of v, until arriving at a leaf. A protocol correctly computes a function f if for every input (x,y) the path defined by (x,y) in T arrives at a leaf labeled by f(x,y). The cost of
14
a protocol is the number of edges in a longest path from the root to a leaf. The deterministic communication complexity of a function f, denoted D(f) is the minimum cost of a protocol which correctly computes f.
One of the most fundamental concepts in deterministic communication complexity is that of a combinatorial rectangle. This is a subset C ⊆ X × Y whichcanbewrittenintheformC =X′×Y′ forsomeX′ ⊆X andY′ ⊆Y. There is a bijection between combinatorial rectangles and Boolean rank-one |X|-by-|Y| matrices—namely, we associate to a rectangle C the Boolean matrix R where R[x,y] = 1 if (x,y) ∈ C and R[x,y] = 0 otherwise. We identify a combinatorial rectangle with its Boolean matrix representation. We say that a combinatorial rectangle C is monochromatic with respect to f if f(x,y) = f(x′,y′) for all pairs (x,y),(x′,y′) ∈ C.
A basic and very useful fact is that a correct deterministic communication protocol for a function f partitions the set of inputs X×Y into combinatorial rectangles which are monochromatic with respect to f.
Definition 6 (partition number) Let X, Y be two finite sets and f : X × Y → {T,F}. Define the partition number, CD(f) as the minimal size of a partition of X × Y into combinatorial rectangles which are monochromatic with respect to f.
Theorem7(partitionbound) Letf:X×Y →{T,F}. Then D(f) ≥ logCD(f).
Proof Let T be a protocol of cost c which correctly computes f. Recall from the definition of a protocol that we describe T as a binary tree of height c. As the height of this tree is c, it has at most 2c many leaves l. For each leaf l, define the set Cl = {(x,y) : (x,y) ∈ X ×Y,T(x,y) → l}. By the notation T (x, y) → l we mean that the path defined by (x, y) arrives at leaf l.
We have now defined at most 2c many sets {Cl} for each leaf of the proto- col. Since the protocol is correct, it is clear that each set Cl is monochromatic with respect to f, and because the functions av(x),bv(y) are deterministic, the sets {Cl} form a partition of X × Y . It remains to show that each Cl is a combinatorial rectangle.
Suppose that (x, y′), (x′, y) ∈ Cl. This means that the paths described by (x, y′), (x′, y) in T coincide. We will show by induction that (x, y) follows
15
this same path and so (x, y) ∈ Cl as well. This is clearly true after 0 steps as all paths begin at the root. Suppose that after k steps the path described by (x, y), (x, y′), (x′, y) have all arrived at a node v. If this is an Alice node then both (x,y) and (x,y′) will move to the child of v indicated by av(x); if this is a Bob node, then both (x,y) and (x′,y) will move to the child of v indicated by bv(y). In either case, the paths described by (x, y), (x, y′), (x′, y) still agree after k + 1 steps, finishing the proof. The reader can verify that a set for which (x,y′),(x′,y) ∈ Cl implies (x,y) ∈ Cl, is a combinatorial rectangle.
The partition bound is a relaxation of deterministic communication com- plexity. A correct deterministic protocol leads to a “tree-like” partition of f into monochromatic combinatorial rectangles, whereas the partition bound allows an arbitrary partition. This relaxation, however, remains relatively tight.
Theorem 8 (Aho, Ullman, Yannakakis [AUY83]) Let f : X × Y → {T,F} be a function, then
D(f) ≤ (log(CD(f)) + 1)2.
We will see a proof of a stronger version of this theorem in Chapter 3. Kushilevitz et al. [KLO96] exhibited a function for which D(f) ≥ 2 log CD(f), currently the largest such gap known.
The partition bound is a relaxation of communication complexity which is guaranteed to give relatively tight bounds. On the negative side, the par- tition bound is hard to compute. Counting the number of 1-rectangles in a smallest monochromatic partition is equivalent to the biclique partition problem, which is NP-hard [JR93]. While this says nothing about the abil- ity of humans to compute the partition bound for communication problems of interest, experience demonstrates the partition bound is also difficult to compute in practice.
We now look at further easier-to-compute relaxations of the partition bound coming from linear algebra. Consider the Boolean communication matrixcorrespondingtof :X×Y →{T,F},denotedBf. Thisisa|X|-by- |Y|matrixwhereBf[x,y]=1iff(x,y)=T andAf[x,y]=0iff(x,y)=F. Denote by B ̄f the communication matrix corresponding to the negation of f.
The partition bound leads us immediately to one of the most important lower bound techniques in deterministic communication complexity, the log rank bound, originally developed by Mehlhorn and Schmidt [MS82].
16
Theorem 9 (log rank bound) Let f : X×Y → {T,F} be a function and Bf the Boolean communication matrix for f. Then
D(f ) ≥ log(rank(Bf ) + rank(B ̄f )).
Proof By Theorem 7, if D(f) = c, then there exists a partition of |X|×|Y | into at most 2c many combinatorial rectangles which are monochromatic with respect to f. Consider such an optimal partition P.
A monochromatic rectangle of f either has all entries equal to zero or all entries equal to one— say that there are Z all zero rectangles and O all-one rectangles in the partition P . We clearly have O + Z ≤ 2c.
With each all-one rectangle Ri in P we associate a rank-one Boolean matrix uivit. Naturally
O
B f = u i v it ,
i=1
where we sum over the all-one rectangles in P. By subadditivity of rank, we find that rank(Bf ) ≤ O. A similar argument shows that rank(B ̄f ) ≤ Z, giving the theorem.
Remark 10 We can also consider the sign matrix Af corresponding to the function f, where Af[x,y] = −1 if f(x,y) = T and Af[x,y] = 1 if f(x,y) = F . By a very similar argument one can show that D(f ) ≥ log rank(Af ).
Recall that the trivial protocol for a function f : {0,1}n×{0,1}n → {T,F} requires n + 1 many bits. Whereas the log rank bound with a sign matrix can show bounds of size at most n, the Boolean form of the log rank bound can sometimes give bounds of size n + 1, satisfyingly showing that the trivial protocol is absolutely optimal.
We see that the log rank bound relaxes the bound from Theorem 7 in two ways. First, rank is the smallest k such that A = ki=1 xiyit, where xi, yi are allowed to be arbitrary real vectors, not Boolean vectors as is required in the partition bound; second, the rank one matrices xiyit,xjyjt are allowed to overlap, whereas the partition bound looks at the size of a smallest partition. What we give up in strength of the bound, we gain in ease of application as matrix rank can be computed in time polynomial in the size of the matrix.
Let us see an example of the log rank bound in action. We return to the problem of Alice and Bob arranging a meeting, the SET INTERSECTION
17
problem. It will actually be more convenient to study the complement of this problem, the DISJOINTNESS function. It is clear that in the deterministic case, a problem and its complement have the same complexity. The Boolean communication matrix for the DISJOINTNESS function on one bit is
1 1 DISJ1= 1 0 .
The columns and rows of DISJ1 are labeled by the two possible inputs 0, 1 in that order. Now consider the communication matrix for the problem on
two bits
We see that DISJ2 = DISJ1⊗DISJ1 is the tensor product of DISJ1 with itself.
This is because taking the tensor product of two Boolean matrices evaluates
the AND of their respective inputs. We can easily check that the matrix
DISJ1 has full rank. Thus the rank of the disjointness function on k bits,
DISJk = DISJ⊗k is 2k as rank is multiplicative under tensor product. Now 1
applying Theorem 9, we find that the deterministic communication complex- ity of the disjointness problem on k inputs is at least k + 1. This shows that the trivial protocol is optimal in the case of SET INTERSECTION.
2.1 Log rank conjecture
One of the most notorious open problems in communication complexity is the log rank conjecture. This conjecture asserts that the log rank bound is faithful, i.e. that it is polynomially related to deterministic communication complexity.
Conjecture 11 (Lovász and Saks [LS88]) There exists a constant c such that for any function f
D(f ) ≤ (log rank(Af ))c + 2.
The log rank conjecture actually has its origins in graph theory. Let G = (V,E) be a graph, the chromatic number χ(G) of G is the size of a smallest partition of the vertices of G into “color” classes such that there is no edge between vertices in the same class. The adjacency matrix AG
18
1 1 1 1 DISJ2 =1 0 1 0.
1 1 0 0 1000
of G is a |V|-by-|V| Boolean matrix where AG[v,w] = 1 if (v,w) ∈ E and AG[v, w] = 0 otherwise.
It was conjectured that the rank of the adjacency matrix of a simple graph is an upper bound on its chromatic number, that is χ(G) ≤ rank(AG). This conjecture was made independently by van Nuffelen [Nuf76] and by the conjecture generating computer program Graffiti [Faj88]. This conjecture was disproved by Alon and Seymour [AS89], who gave an example of a graph on 64 vertices with chromatic number 32 and rank 29.
Lovász and Saks [LS88] made the log rank conjecture in the above form, and showed that it is equivalent to the statement that (log rank(AG))c is an upper bound on log χ(G), for some constant c.
Several examples that separate communication complexity and log rank have been given. Raz and Spieker [RS95] gave an example with a super-linear separation between communication complexity and log rank, and Nisan and Wigderson [NW95] showed the largest separation currently known: a func- tion f where D(f) ≥ (logrank(Af))1.63 (this constant was obtained via a slight improvement due to Kushilevitz, see [NW95]).
On the positive side, we know that D(f) ≤ rank(Af), but this is expo- nentially far from the goal of the conjecture. In fact, we can also upper bound communication complexity by the rank over GF (2). This is sometimes tight, e.g. for the inner product function.
Theorem 12 Let B be a Boolean matrix and rank2(B) be the rank of B over GF(2). Then
D(f) ≤ rank2(Bf ) + 1
Proof Let r = rank2(Bf). We can factor Bf = XtY where X,Y are Boolean valued matrices with r many rows. On input i, Alice can simply send Xi, the column of X labeled by i, to Bob with r many bits. Bob can then take the inner product of Xi with Yj—the column labeled by his input j—to determine Bf [i, j]. With one more bit Bob sends the value of Bf [i, j] to Alice.
2.2 Nonnegative rank
Yannakakis [Yan91] introduced to communication complexity the notion of nonnegative rank.
19
Definition 13 Let M be a nonnegative matrix. The nonnegative rank of M, denoted rank+(A) is the least r such that
for nonnegative vectors xi, yi.
r
M = x i y it
i=1
We clearly have rank(M) ≤ rank+(M) for a nonnegative matrix M. For a Boolean matrix B, notice that the rank-one decomposition of B induced by a successful protocol as in Theorem 9 only uses nonnegative (in fact Boolean) matrices, and so log rank+(Bf ) ≤ D(f). While nonnegative rank gives stronger lower bounds, it is also NP-hard to compute [Vav07] and we are not aware of any lower bounds which actually use nonnegative rank in practice.
Lovász shows that max{log rank+(Bf ), log rank+(J − Bf )}, where J is the all-ones matrix, faithfully represents deterministic communication com- plexity. In fact, he gives the following stronger bound.
Theorem 14 (Lovász [Lov90], Corollary 3.7)
D(f) ≤ (log(rank+(Bf )) + 1)(log(rank(J − Bf )) + 1).
We will see the proof of this theorem in Section 3.2 in the chapter on non- deterministic communication complexity.
Theorem 14 suggests the following equivalent formulation of the log rank conjecture as a purely mathematical question:
Theorem 15 The log rank conjecture holds if and only if there is a constant c such that for all Boolean matrices B
log rank+(B) ≤ (log rank(B))c. 2.3 Norm based methods
We have seen the partition bound which is a lower bound on deterministic communication complexity, and the rank lower bound which in turn relaxes the partition bound. We now survey another family of lower bound methods based on (matrix and vector) norms.
20
Although sometimes requiring nontrivial arguments, it turns out that all the norm based methods discussed in this section in fact lower bound matrix rank. This prompts the question: why study these norm based tech- niques if the rank method gives a better lower bound and is, at least from a theoretical perspective, easy to compute? The real advantage of these norm based methods will only be seen later on in the study of randomized and multiparty models. While the rank method can also be appropriately extended to these models, it becomes much more difficult to compute; the convexity properties of norm based methods make their extensions to these models more tractable. We go ahead and introduce the norm based methods in the context of deterministic communication complexity where the situa- tion is simpler, and later discuss how they can be adapted to more powerful models.
We repeatedly use the l1, l2 and l∞ norms, hence we recall their def- inition here: for a vector v ∈ Rn and a real number p ≥ 1 the lp norm of v, denoted ∥v∥p, is defined as ∥v∥p = (ni=1 |v[i]|p)1/p. We see then that ∥v∥1 = i |v[i]|, and ∥v∥2 = (i |v[i]|2)1/2. The limiting case is ∥v∥∞ = maxi |v[i]|. The reader should keep in mind that matrices and functions to R can be naturally viewed as vectors, whence taking their lp norms is likewise natural.
2.3.1 Trace norm
We begin with a simple lower bound on the rank. Let A be a m-by-n real matrix. The matrix AAt is positive semidefinite, hence it has nonnegative real eigenvalues. We denote these eigenvalues by λ1(AAt) ≥ · · · ≥ λm(AAt). The ith singular value of A, denoted σi(A), is defined by σi(A) = λi(AAt). In many ways, singular values can be seen as a generalization of eigenvalues to non-square matrices. If A is symmetric, then its singular values are just the absolute values of its eigenvalues. While not every matrix can be diago- nalized, every matrix A can be factored as A = UΣV where U is a m-by-m unitary matrix, V is a n-by-n matrix and Σ is a diagonal matrix with the singular values of A on its diagonal. This shows in particular that the rank of A is equal to the number of nonzero singular values.
Definition 16 (trace norm) Let A be a m-by-n matrix, and let σ = (σ1, . . . , σrank(A)) be the vector of nonzero singular values of A. The trace norm of A, denoted
∥A∥tr is
∥A∥tr = ∥σ∥1 We also make use of the Frobenius norm.
21
Definition 17 (Frobenius norm) Let A be a m-by-n matrix, and let σ = (σ1, . . . , σrank(A)) be the vector of nonzero singular values of A. The Frobe- nius norm of A, denoted ∥A∥F is
∥A∥F = ∥σ∥2.
As the number of nonzero singular values is equal to the rank of A, the
Cauchy-Schwarz inequality gives
rank(A)
∥A∥tr = σi(A) ≤ rank(A)
σi2(A).
i=1
Rearranging, this gives us the following lower bound on the rank.
rank(A) ≥ ∥A∥2tr . ∥A∥2F
In this section, it is convenient to consider the sign version of the commu- nication matrix. The reason is that, for a sign matrix A, the Frobenius norm simplifies very nicely. Notice that as the trace of a symmetric matrix is the sum of its eigenvalues, we have ∥A∥2F = Tr(AAt). By explicitly writing the diagonal elements of AAt, we also see that Tr(AAt) = i,j |A[i, j]|2 = ∥A∥2. Hence for a m-by-n sign matrix A, we have ∥A∥2F = mn. This gives the following lower bound, which we call the trace norm method.
Theorem 18 (trace norm method) Let A be a m-by-n sign matrix. Then D(A) ≥ log rank(A) ≥ log ∥A∥2tr
mn
As an example, let us compute the trace norm bound for the INNER PRODUCT function. Recall that in this case Alice and Bob wish to evaluate the parity of the number of positions for which xi = yi = 1. The sign matrix of this function turns out to be the familiar Sylvester construction of Hadamard matrices 1. If we look at the INNER PRODUCT function on just one bit we have the matrix
1 1 H1= 1 −1
1 A Hadamard matrix is an orthogonal sign matrix. That is, a sign matrix whose rows are pairwise orthogonal.
22
i=1
Since taking the tensor product of sign matrices corresponds to taking the
parity of their inputs, the communication matrix of the INNER PRODUCT
function on k bits is Hk = H⊗k. It is not hard to prove that the matrix Hk 1
is orthogonal, i.e. satisfies HkHkt = 2kIk, where Ik is the 2k-by-2k identity matrix. One can simply verify that H1 is orthogonal, and that the tensor product of two orthogonal matrices is also orthogonal. It follows then that Hk has 2k singular values, all equal to 2k/2, and so its trace norm is 23k/2. Thus, applying the trace norm method, we obtain a bound of k, implying that the trivial protocol is essentially optimal for the INNER PRODUCT function.2
2.3.2 γ2 norm
As a complexity measure, the trace norm method suffers from one drawback: it is not monotone with respect to function restriction. In other words, it sometimes gives a worse bound on a restriction of a function than on the function itself. An example of this is the matrix
Hk Jk JJ,
kk
where Jk is the 2k-by-2k matrix whose entries are all equal to one. The trace norm of this matrix is at most 23k/2 + 3 · 2k . Since in the trace norm method we normalize by the matrix size, in this case 22k+2, this method gives a smaller bound on the above matrix than on the submatrix Hk.
To remedy this, we seek a way to focus on the “difficult” part of the matrix. We do this by putting weights on the entries of the matrix in the form of a rank-one matrix uvt. The weighted matrix is then the entrywise product of A with uvt, denoted A◦uvt. It is easy to check that rank(A◦uvt) ≤ rank(A), and so
rank(A) ≥ max ∥A ◦ uvt∥2tr (2.1) u,v ∥A ◦ uvt∥2F
for any u, v. This new bound is monotone with respect to function restriction. If A is a sign matrix, then it is particularly nice to choose u,v to be unit vectors, for then ∥A ◦ uvt∥F = ∥u∥2∥v∥2 = 1. This motivates the following definition
2For this example it is even easier to argue about the rank as HkHkt = 2kIk means that Hk is full rank. The advantage of the trace norm argument is that it can be easily extended to the randomized case, see Example 65.
23
Definition 19 (γ2 norm) For a matrix A we define γ2(A) = max ∥A ◦ uvt∥tr
u,v:∥u∥2=∥v∥2=1
The connection of γ2 to communication complexity is given by the fol-
lowing theorem which follows from Equation (2.1).
Theorem 20 Let A be a sign matrix. Then rank(A) ≥ γ2(A)2.
While the γ2 norm has been introduced relatively recently to complexity theory [LMSS07, LS09c], it has been around in matrix analysis for a while. Tracing its heritage is somewhat difficult because of its many different names: in the matrix analysis community it has been called by various combinations of “Hadamard/Schur operator/trace norm.” Schur in 1911 [Sch11] showed that if a matrix A is positive semidefinite, then γ2(A) = maxiA[i,i]. It should be noted that unlike the trace norm, γ2 is not a matrix norm as it is not true in general that γ2(AB) ≤ γ2(A)γ2(B).
That γ2 is a norm, namely that it satisfies γ2(A+B) ≤ γ2(A)+γ2(B), can be seen most easily by the following equivalent formulation as a minimization problem. A proof of the equivalence of this definition with the one given above can be found in [LSŠ08].
Theorem 21 For any real m-by-n matrix M
γ2(M) = min r(X)r(Y ) (2.2)
X,Y :XY t=M
where r(X) is the largest l2 norm of a row of X.
Let us see that the optimization problem of Theorem 21 can be written as a semidefinite program as follows.
γ2(M) = minc cI ≽ Z ◦ I
0 Jm,n 0 M Z◦Jn,m 0 =Mt 0
Z ≽ 0.
Here Jm,n indicates the m-by-n all-ones matrix, and I the (m+n)-by-(m+n) identity matrix.
24
Let X, Y be an optimal solution to Equation (2.2). Notice that by mul- tiplying X by a suitable constant and dividing Y by the same constant, we may assume that r(X) = r(Y ). Now let
X Xt Z=YY.
By construction this matrix is positive semidefinite, and is equal to M on the off diagonal blocks as M = XY t. Furthermore, the diagonal entries of Z areatmostmax{r(X)2,r(Y)2}≤γ2(M).
For the other direction, given an optimal solution Z to the above semidef- inite program, we can factor Z as
X Xt Z=YY,
for some m-by-k matrix X and n-by-k matrix Y . Then the constraints of the semidefinite program give that XY t = M and that max{r(X)2, r(Y )2} ≤ c, the value of the program.
Finally, from this semidefinite programming formulation of γ2, it is easy to verify that γ2(M1 + M2) ≤ γ2(M1) + γ2(M2). Let X1 and X2 be semidef- inite matrices attaining the optimal value in this program for the matrices M1 and M2 respectively. Recall that the sum of two semidefinite matrices is also a semidefinite matrix. It is easy to see that X1 + X2 is a feasible instance of the above program for M1 + M2, achieving the value γ2(M1) + γ2(M2). The semidefinite programming formulation also shows that γ2(M) can be computed up to error ε in time polynomial in the size of the matrix and log(1/ε).
2.3.3 μ norm
In this section we introduce another norm useful for communication complex- ity, which we denote by μ. While the motivation for this norm is somewhat different from that of γ2, it surprisingly turns out that μ and γ2 are equal up to a small multiplicative constant.
Recall the “partition bound” (Theorem 9) and the “log rank lower bound” (Theorem 7). A basic property we used is that a sign matrix A can be written as
2D(A)
A = αiRi
i=1
25
where each αi ∈ {−1, 1} and each Ri is a rank-one Boolean matrix, which we also call a combinatorial rectangle. As each αi ∈ {−1, 1} we of course have i |αi| = 2D(A).
The log rank lower bound is a relaxation of the partition bound where we express A as the sum of arbitrary real rank-one matrices instead of just Boolean matrices. The following definition considers a different relaxation of the partition bound, where we still consider a decomposition in terms of Boolean matrices, but count their “weight” instead of their number.
Definition 22 (μ norm) Let M be a real matrix.
μ(M) = min{|αi| : M = αiRi},
αi ∈R
ii
where each Ri is a combinatorial rectangle.
It is not hard to check that μ is a norm. Notice that μ(M) ≥ γ2(M) as any combinatorial rectangle Ri satisfies γ2(Ri) ≤ 1.
Applying similar reasoning as for the log rank bound, we get
Theorem 23 Let A be a sign matrix, then D(A) ≥ log μ(A).
2.3.4 The nuclear norm
It is sometimes useful to consider a slight variant of the norm μ where instead of rank-one Boolean matrices we consider rank-one sign matrices.
Definition 24 (ν norm) Let M be a real matrix,
ν(M) = min{|αi| : M = αixiyit, for xi,yi sign vectors}
αi ∈R
ii
For readers with some background on norms, the norm ν is a nuclear norm [Jam87]. Nuclear norms are dual to operator norms which we also encounter later on. The norms μ and ν are closely related.
Claim 25 For every real matrix M,
ν(M) ≤ μ(M) ≤ 4ν(M).
26
Proof Since both μ and ν are norms, it is enough to show that 1. ν(srt) ≤ 1 for every pair of Boolean vectors s and r.
2. μ(xyt) ≤ 4 for every pair of sign vectors x and y.
For the first inequality we consider the following correspondence between sign vectors and Boolean vectors. Given a Boolean vector s we denote s ̄ = 2s − 1 (Here 1 is a vector of ones). Note that s ̄ is a sign vector.
Now, s = 1 (s ̄ + 1), and therefore 2
ν(srt)= 1ν((s ̄+1)(r ̄+1)t)≤1. 4
To prove the second inequality simply split the sign vector x to two Boolean vectors depending on whether xi is equal to 1 or −1, and similarly for y. The rank-one sign matrix xyt can be written this way as the linear combination of 4 combinatorial rectangles with coefficients 1 and −1.
2.3.5 Dual norms
We have now introduced three norms γ2,μ,ν and seen that they give lower bounds on deterministic communication complexity. For actually proving lower bounds via these methods, a key role is played by their dual norms. We go ahead and define these dual norms here to collect all the definitions in one place and as this is also the easiest way to see that γ2 and ν are related by a constant factor. As we have already seen that μ and ν are equivalent up to a factor of 4, this means that all three norms are related by a constant factor.
For any arbitrary norm Φ, the dual norm, denoted Φ∗, is defined as Φ∗(M)= max ⟨M,Z⟩.
Z :Φ(Z )≤1
Let us first consider ν ∗ , the dual norm of ν . If a matrix Z satisfies ν(Z) ≤ 1, then it can be written as Z = α1Z1 +…+αpZp where each Zi is a rank-one sign matrix and |αi| ≤ 1. Thus
ν∗(M) = max αi⟨M,Zi⟩. {αi} i
Pi |αi|≤1
27
The maximum will be achieved by placing weight 1 on the rank-one sign matrix Zi which maximizes ⟨M, Zi⟩. Thus we have
ν∗(M) = max M[i, j] x[i] · y[j]. (2.3) x∈{−1,+1}m
y∈{−1,+1}n i,j
The dual norm ν∗(M) is also known as the infinity-to-one norm ∥M∥∞→1.
This is because one can argue that
ν∗(M)= max M[i,j]x[i]·y[j]= max ∥My∥1. x:∥x∥∞≤1 i,j y:∥y∥∞≤1 y:∥y∥∞≤1
In words, the first equality says that the optimal x, y will have each entry in {−1, +1}.
A similar argument can be used to see that
μ∗(M)= max M[i,j]x[i]·y[j]. (2.4) x∈{0,1}m
y∈{0,1}n i,j
This norm is also known as the cut norm [FK99, AN06], as xtMy represents the weight of edges between the sets with characteristic vectors given by x and y.
Both the ν∗ and μ∗ norms are NP-hard to compute [AN06]. The dual norm γ2∗ of γ2 can be viewed as a natural semidefinite relaxation of these norms. In fact, γ2∗ is exactly the quantity studied by Alon and Naor [AN06] to give an efficient approximation algorithm to the cut norm, and is also closely related to the semidefinite relaxation of MAX CUT considered by Goemans and Williamson [GW95].
We can derive a convenient expression for γ2∗ as we did with ν∗. If a matrix Z satisfies γ2(Z) = 1, then we can write Zi[k,l] = ⟨xk,yl⟩ for a collection of unit vectors {xk},{yl}. Thus
γ2∗(M) = max M[i,j]⟨xi,yj⟩. (2.5) {xi},∥xi∥2≤1 i,j
{yi },∥yi ∥2 ≤1
It is clear that γ2∗(M) ≥ ν∗(M) as the maximization is taken over a larger set. Grothendieck’s famous inequality says that γ2∗ cannot be too much larger.
Theorem 26 (Grothendieck’s Inequality) There is a constant KG such that for any matrix M
γ2∗(M) ≤ KG ν∗(M). 28
The current best bounds on KG show that 1.67… ≤ KG ≤ 1.78… [Ree91, Kri79].
It is not hard to check that two norms are equivalent up to a constant factor if and only if the corresponding dual norms are. Thus summarizing, we have the following relationship between γ2, ν, μ:
Corollary 27 ([LS09b]) For any matrix M
γ2(M) ≤ ν(M) ≤ μ(M) ≤ 4KGγ2(M).
One consequence of this relationship is that rank(A) = Ω(μ(A)2) for a sign matrix A, a fact which is not obvious from the definition of μ.
We will discuss all these norms in more detail in Chapter 4 on randomized communication complexity.
2.4 Summary
Complexity measures Let A be a sign matrix, and denote by M a real matrix.
• rank(M) – the rank of a the matrix M over the real field.
• rank2(A) – the rank of the matrix A over GF(2).
• rank+(M) – the nonnegative rank of M.
• D(A) – the deterministic communication complexity of A (equivalently, the communication complexity of the corresponding function).
• ∥M∥p = (i,j |M[i,j]|p)1/p – the lp norm.
• ∥M∥tr – the trace norm of M.
• ∥M∥F – the Frobenius norm of M.
• γ2(M) = maxu,v:∥u∥2=∥v∥2=1 ∥A ◦ uvt∥tr – the γ2 norm.
• μ(M) – the dual norm to the cut norm.
• ν(M) – the nuclear norm of M.
29
Relations For every m × n sign matrix A and a real matrix M
• rank2(A) ≤ rank(A) ≤ rank+(A). • log rank+(A) ≤ D(A) ≤ rank2(A). • D(A)≤logrank(A)logrank+(A).
• rank(A) ≥ γ2(M)2 ≥ ∥A∥2tr . mn
• ∥M∥F =∥M∥2.
• γ2(M) ≤ ν(M) ≤ μ(M) ≤ 4KGγ2(M).
30
Chapter 3
Nondeterministic communication complexity
As with standard complexity classes, we can also consider a nondeterminis- tic version of communication complexity. It turns out that nondeterministic communication complexity has a very nice combinatorial characterization and in some ways is better understood than deterministic communication complexity. In particular, nondeterministic communication complexity pro- vides a prime example of the implementation of the “three-step approach” outlined in the introduction.
We now formally define nondeterministic communication complexity. Let f:X×Y →{T,F}beafunction,andletL={(x,y):f(x,y)=T}. A successful nondeterministic protocol for f consists of functions A : X × {0,1}k →{0,1}andB:Y ×{0,1}k →{0,1}suchthat
1. For every (x,y) ∈ L there is z ∈ {0,1}k such that A(x,z)∧B(y,z) = 1.
2. Forevery(x,y)̸∈L,forallz∈{0,1}k,itholdsA(x,z)∧B(y,z)=0.
The cost of such a protocol is k, the length of the message z. We define N1(f) to be the minimal cost of a successful nondeterministic protocol for f. We let N0(f) = N1(¬f) and N(f) = max{N0(f),N1(f)}.
One can equivalently think of a nondeterministic protocol as consisting of two stages—in the first stage both players receive a message z, and in the second stage they carry out a deterministic protocol—the cost now being the length of z plus the communication in the deterministic protocol. The definition we have given is equivalent to this one as the transcript of the deterministic protocol can always be appended to the witness z with each
31
party accepting if the transcript agrees with what they would have said in the protocol, given what the other party said.
Let us revisit the SET INTERSECTION problem. If someone with knowledge of both Alice’s and Bob’s schedule tells them they can meet Thursday at noon, they can easily verify this is true. On the other hand, if they have no time in common to meet, every suggestion of the prover will lead to a conflict. Thus for the SET INTERSECTION problem f we have N1(f) ≤ ⌈log n⌉.
Besides the analogy with nondeterministic complexity classes, another motivation for studying nondeterministic complexity is that it has a very natural combinatorial characterization.
Definition 28 Let f : X × Y → {0, 1} be a function, and let b ∈ {0, 1}. We denote by Cb(f) the smallest cardinality of a covering of f−1(b) by combi- natorial rectangles. To illustrate, a covering of f−1(1) is a set of rank-one Boolean matrices {Ri}i∈I such that: if f(x,y) = 1 then Ri[x,y] = 1 for some i∈I, and if f(x,y)=0 then Ri[x,y]=0 for all i∈I.
We can also view this definition in graph theoretic terms. An arbitrary Boolean matrix B can be thought as the “reduced” adjacency matrix of a bipartite graph, where rows are labeled by vertices of one color class and columns by vertices of the other color class. Then C1(B) is the size of a smallest covering of the edges of B by bipartite cliques. It is known that this is NP-hard to compute in the size of the graph [Orl77], and even NP-hard to approximate within a factor of nδ for some δ > 0 for a n-vertex graph [LY94].
Theorem29 Letf:X×Y →{0,1}beafunction, N1(f) = log C1(f)
Proof First we show that N1(f) ≤ log C1(f). Let {Ri} be a covering of f−1(1) of minimal cardinality. If f(x,y) = 1, the players receive the name i of a rectangle Ri = X′ × Y ′ such that Ri[x, y] = 1. Alice then checks that x ∈ X′ and Bob checks that y ∈ Y′. If this is indeed the case then they accept. If f(x,y) = 0 then by definition of a covering no such index exists.
Now consider the opposite direction. Let k = N1(f) and let fA : X ×{0, 1}k → {0, 1}, fB : Y ×{0, 1}k → {0, 1} be functions realizing that the nondeterministiccomplexityoffisk.LetRz ={(x,y):fA(x,z)∧fB(y,z)= 1}. This is a rectangle, and by definition of success of a protocol if f (x, y) = 1 then (x,y) ∈ Rz for some z and if f(x,y) = 0 then (x,y) ̸∈ Rz for all z. This
32
gives a covering of size 2k.
3.1 Relation between deterministic and nondeter- ministic complexity
Many open questions in communication complexity revolve around showing that the combinatorial and linear-algebraic lower bound techniques we have developed are faithful. The next theorem, due to Aho, Ullman, and Yan- nakakis, is one of the deepest results we know in this regard. It shows how to turn a monochromatic rectangle covering of a matrix into a deterministic algorithm. Alternatively, it says that if a function has both an efficient non- deterministic protocol and an efficient co-nondeterministic protocol, then it has an efficient deterministic protocol. This is quite different from what we expect in terms of traditional complexity classes.
Theorem 30 (Aho, Ullman, Yannakakis [AUY83]) Let f : X × Y → {0, 1} be a function, then
D(f) ≤ (N0(f) + 1)(N1(f) + 1).
We will present a tighter version of this theorem due to Lovász [Lov90], which follows the same basic outline but replaces N1(f) with a smaller quan- tity. For a Boolean matrix B, define ρ1(B) such that ρ1(B) − 1 is equal to the largest (after possibly permuting rows and columns) submatrix of B with ones on the diagonal and zeros below the diagonal. Notice that ρ1(B) is at most N1(B) + 1, and also is at most rank(B) + 1.
Theorem 31 (Lovász) Let B be a Boolean matrix. Then D(B) ≤ (log(ρ1(B)) + 1)(N0(B) + 1).
33
Proof The proof is by induction on ρ1(B). Suppose that ρ1(B) = 1. In this case, B does not contain any ones at all and so is the all zeros matrix and has D(B) = 1. This finishes the base case of the induction.
Let R1,…,RM be a covering of the zeros of B which realizes N0(B) = ⌈logM⌉. Let Si denote the submatrix of rows of B which are incident with Ri, and similarly Ti the submatrix of columns of B incident with Ri.
The key observation to make is that ρ1(Si) + ρ1(Ti) ≤ ρ1(B) for each i. Thus we may assume without loss of generality that ρi(Si) ≤ ρ(B)/2 for i = 1, . . . , N with N ≥ M/2 and ρi(Ti) ≤ ρ(B)/2 for i = N + 1, . . . , M.
The protocol goes as follows. On input x, Alice looks for a rectangle Ri for i = 1,…,N which intersects with the xth row of B. If such a rectangle exists she sends to Bob the bit ‘0’ followed by the index of the rectangle and the round ends. If no such rectangle exists, she sends ‘1.’
If Bob receives the message ‘1’ from Alice, he looks for a rectangle Ri for i = N +1,…,M which intersects the column labeled by his input y. If yes, he sends a ‘0’ followed by the name of such a rectangle, otherwise he gives the answer ‘1.’
We analyze the cost of this protocol based on the outcome of three cases. In each case, the protocol will either output the answer, or reduce the search to a submatrix where the induction hypothesis may be applied.
Case 1: Both Alice and Bob output ‘1.’ In this case, (x, y) does not lie in any zero rectangle of the covering, thus the answer must actually be ‘1.’
Case 2: Alice outputs ‘0’ and the name of a rectangle Ri. In this case, the protocol continues in the submatrix Ai. As ρ(Ai) ≤ ρ(Bi)/2 we can apply the induction hypothesis to see that the communication complexity of Ai is at most
(log(ρ(Ai)) + 1)(N0(Ai) + 1) ≤ log(ρ(B))(N0(B) + 1).
Adding in the length of Alice’s initial message of 1+N0(B) we get that the total communication complexity of B is at most (log(ρ(B))+1)(N0(B)+1) as desired.
Case 3: Alice outputs ‘1’ and Bob outputs ‘0’ and the name of a rectangle. This case is works in the same way as case 2. Notice that the communica- tion for the initial round is again N0(B) + 1. We have one bit from Alice’s message and 1 + (N0(B) − 1) for Bob’s message, as there are less than M/2
34
possible rectangle labels he might output.
This theorem can be tight. Jayram, Kumar, and Sivakumar [JKS03] give an example of a function f where N0(f) = N1(f) = O(√n) and D(f) = Ω(n).
3.2 Relation with nonnegative rank
Recall the notion of nonnegative rank introduced earlier. Yannakakis [Yan91] showed that nondeterministic communication complexity is a lower bound on the logarithm of nonnegative rank.
Theorem 32 (Yannakakis [Yan91]) Let f : X × Y → {0, 1} be a func- tion, and let B be a Boolean matrix where B[x,y] = f(x,y). Then
N1(f) ≤ log rank+(B)
Proof Suppose that rank+(B) = r. Then we have a decomposition of B as
r
B = x i y it i=1
where xi, yi are nonnegative vectors. Define new vectors x′i, yi′ by 1 if xi[j] > 0
x′i[j] = 0 otherwise
and similarly for yi′. Then i x′i(yi′)t will be zero whenever B is, and will be
at least 1 whenever B is equal to 1.
This result, together with Theorem 31, implies that D(f ) ≤ (log(rank(Bf ))+
1))(log(rank+(J − Bf )) + 1), where J is the all-ones matrix. 3.3 Fractional cover
As in the case of the rectangle bound, we can similarly write the cover number as an integer program. Let f : X × Y → {0,1} be a function. Then we see
35
that
C1(f) = minαi αi
αiRi[x,y] ≥ 1 for all (x,y) ∈ f−1(1) i
αiRi[x,y] = 0 for all (x,y) ∈ f−1(0) i
αi ∈ {0, 1},
where each Ri is a combinatorial rectangle. Karchmer, Kushilevitz, and Nisan [KKN95] considered showing lower bounds on nondeterministic com- munication complexity by the linear programming relaxation of the cover number.
Definition 33 (Fractional cover) Let f : X × Y → {0, 1} be a function, the fractional cover of f−1(1) is
C ̄1(f) = minαi αi
αiRi[x,y] ≥ 1 for all (x,y) ∈ f−1(1) i
αiRi[x,y] = 0 for all (x,y) ∈ f−1(0) i
αi ≥ 0,
where each Ri is a combinatorial rectangle.
Notice that the size of this program can be exponential in |X| + |Y | since there is a variable αi for every combinatorial rectangle.
The fractional cover implements the first step of the “three-step ap- proach.” It is a convex real-valued function and clearly C ̄ 1 (f ) ≤ C 1 (f ). Moreover, C ̄1(f) turns out to give a tight bound on C1(f). Lovász [Lov75] has shown quite generally that the linear program relaxation of set cover gives a good approximation to the integral problem. Karchmer, Kushile- vitz, and Nisan [KKN95] observed that this has the following application for nondeterministic communication complexity.
Theorem 34 (Karchmer, Kushilevitz, and Nisan [KKN95]) Let f : {0, 1}n × {0, 1}n → {0, 1} be a function. Then
log C ̄1(f) ≤ N1(f) ≤ log C ̄1(f) + log n + O(1). 36
The fact that nondeterministic communication complexity is tightly char- acterized by a linear program implies other nice properties as well. Lovász [Lov75] also showed that the fractional cover program obeys a product prop- erty: C ̄1(A ⊗ B) = C ̄1(A)C ̄1(B) for every pair of Boolean matrices A and B. Karchmer, Kushilevitz, and Nisan used this result to obtain the following consequence for nondeterministic communication complexity.
Theorem 35 (Karchmer, Kushilevitz, and Nisan [KKN95]) Let A, B be any two Boolean matrices of size 2n-by-2n. Then
N1(A ⊗ B) ≥ N1(A) + N1(B) − 2 log n − O(1).
Karchmer, Kushilevitz, and Nisan also carried out the second step of the three-step formulation to give an equivalent “max” formulation of C ̄1(f) convenient for showing lower bounds. To see this, let us first write the program for C ̄1(f) more compactly in matrix notation. Let A be a Boolean matrix with rows labeled by elements of f−1(1) and columns labeled by 1- monochromatic rectangles, and where A[(x, y), Ri] = 1 if and only if (x, y) ∈ Ri. Then the program from Definition 33 can be written
C ̄1(f) = min 1tα α
Aα ≥ 1 α ≥ 0.
Here 1, 0 stand for the all-one vector and all zero vector respectively, where the dimension can be inferred from the context.
Now consider the following maximization problem over a vector μ of dimension |f−1(1)|.
C1(f) = max 1tμ ̄μ
Atμ ≤ 1 μ ≥ 0.
In this program one assigns nonnegative weight μx,y to every input (x, y) with f(x,y) = 1, such that the total weight given to any 1 monochromatic rectangle is at most 1.
It is easy to see that C1(f) ≤ C ̄1(f). Indeed, let μ satisfy the constraints ̄
of the former and α satisfy the constraints of the latter. Then 1tμ ≤ (αtAt)μ = αt(Atμ) ≤ 1tα.
As we will discuss in Chapter 6, using linear programming duality one can
show that in fact C1(f) = C ̄1(f). ̄
37
3.4 Summary
Complexity measures Let A be a Boolean matrix.
• N1(A) – the nondeterministic communication complexity of A.
• N0(A) = N1(J − A), where J is the all-ones matrix.
• N(A) = max{N0(A), N1(A)}.
• C1(A) – the size of a minimal cover of the ones of A by monochromatic rectangles.
• C ̄1(A) – fractional cover.
Relations Let A and B be a pair of Boolean matrices of size 2n-by-2n • D(A) ≤ (N0(A) + 2)(N1(A) + 2).
• N1(A)=logC1(A).
• log C ̄1(A) ≤ N1(A) ≤ log C ̄1(A) + log n + O(1).
• N1(A⊗B)≥N1(A)+N1(B)−2logn−O(1).
38
Chapter 4
Randomized communication complexity
Suppose that Alice and Bob have access to a source of randomness—that is, the next message they send is no longer a deterministic function of their input and prior messages, but can also depend on the outcome of a coin flip. In this case the output of a protocol is no longer fixed by the input, but can depend on the sequence of coin flips. Say that we also relax the requirement that the output of the protocol is always correct, and only require this with high probability. As we shall see in this chapter, for some problems randomness allows vastly more efficient protocols, and the task of proving lower bounds on randomized protocols is correspondingly more challenging.
There are several different versions of randomized communication com- plexity one can consider. First, one can vary the output conditions, and study protocols with no error, one-sided error, or two-sided error. In this survey, we will just consider the two-sided error case. Secondly, one can vary the players’ mode of access to randomness, namely whether randomness is shared or private.
In the shared randomness or public coin model, at the beginning of the protocol Alice and Bob receive a common random string r. There is no bound on how long this random string can be, and its length has no effect on the cost of the protocol. Alice and Bob then perform a deterministic protocol Pr where their messages can depend on the fixed string r. Thus in the public coin model, a randomized communication protocol is simply a probability distribution over deterministic protocols. We say that a randomized protocol P computes a function f with error at most ε if Prr[Pr(x, y) = f(x, y)] ≥ 1−ε for every input (x, y). The cost of a public coin protocol is the maximal cost
39
of any of the deterministic protocols Pr. We let Rε(f) denote the minimal cost of a public coin protocol which computes f with error at most ε.
The next theorem gives a nice equivalent definition of public coin ran- domized communication complexity, in matrix language.
Theorem 36 A Boolean matrix A has randomized communication complex- ity Rε(A) = h in the public coin model, if and only if there is a probability distributionp1,…,pm andBooleanmatricesB1,…,Bm suchthat
1. D(Bi) ≤ h for every i = 1,…,m.
2. ∥A − mi=1 piBi∥∞ ≤ ε.
We wrote Theorem 36 with Boolean matrices, but we also use the corre- sponding steatement for sign matrices. The reader can easily verify that, in the corresponding statement for sign matrices, one only needs to change ε to 2ε in the last inequality.
In the private coin model, Alice and Bob independently receive a random
string which is not seen by the other player. Rather than initially receiving
a random string at the beginning of the protocol, it will be more convenient
to imagine that Alice and Bob flip coins “as they go.” More precisely, let
R be an arbitrary finite set. A private coin protocol is a binary tree where
each internal node is either labeled by a function av : X × R → {0, 1}
or bv : X × R → {0,1}. Leaves are labeled by elements of {0,1}. If a
node v is labeled by av, then on input x Alice outputs 1 with probability
Prr∈R[av(x,r) = 1] and outputs 0 with probability Prr∈R[av(x,r) = 0], and
similarly for nodes labeled by bv. We say that a private coin protocol P
computes a function f : X × Y → {0,1} with error at most ε if for every
input (x, y) the probability that the path traced through the tree arrives at
a leaf labeled by f (x, y) is at least 1 − ε. The cost of a protocol is the height
of the tree, and we denote Rpri(f) the minimal cost of a private coin protocol ε
which computes f with error at most ε.
The first observation about the relative power of these two models is that
R (f) ≤ Rpri(f). This is because in a public coin protocol Alice can simply εε
use the left half of the common random string and Bob the right half to simulate a private coin protocol.
A very nice result by Newman [New91] shows that, at least for the bounded-error case we are interested in, private coin protocols can also sim- ulate public coin protocols without too much overhead.
Theorem 37 (Newman [New91]) Let f : {0, 1}n × {0, 1}n → {0, 1}. For 40
every ε, δ > 0 it holds that
Rpri (f)≤Rε(f)+O(logn−logδ).
We will be concerned with the case where the error probability is a small con- stant, and in this case the theorem essentially says that public coin and pri- vate coin communication complexity are the same up to an additive O(log n) term. 1 For this reason, and as we are primarily concerned with lower bounds, we will focus on the public coin model in this chapter. In par- ticular, when we refer to “randomized communication complexity” without specifying public or private coin, we mean the public coin model.
Before moving on to lower bounds for randomized communication com- plexity, it is first insightful to see an example where randomized protocols can be significantly more powerful than deterministic protocols. Luckily there is a simple example which shows the largest possible gap between determin- istic and randomized complexity, and incidentally also shows an Ω(logn) additive gap between the public and private coin models, also implying that Newman’s theorem can be tight.
Consider the 2n × 2n identity matrix I2n , the Boolean communication matrix for the EQUALITY problem. That is, I2n[x,y] = 1 if x = y and I2n [x, y] = 0 otherwise. As this matrix is full rank, the log rank lower bound of Theorem 9 thus implies that D(I2n ) ≥ n + 1. The public coin randomized communication complexity of this problem on the other hand is Θ(1), and in the private coin model the complexity is Θ(log n).
A randomized protocol that achieves this constant complexity is as fol- lows. Alice and Bob interpret their inputs x and y respectively as elements of Zn2 , and also interpret the shared random string as a tuple of d strings z1, . . . , zd ∈ Zn2 . Using d bits of communication Alice sends to Bob the val- ues ⟨x, zi⟩ ∈ Z2 for i = 1 . . . d. If the corresponding inner products ⟨y, zi⟩ all agree, Bob reports that x = y, and otherwise he announces that x and y are distinct. If x and y are equal this protocol is always correct. If x and y are distinct the output of this protocol is correct with probability 1 − 2−d.
It is not hard to similarly devise an O(logn) complexity private coin protocol for equality, or one can simply invoke Newman’s theorem to see
1Notice that the smaller δ is, the larger the potential gap between these models. In the unbounded-error model, where the players need only succeed with probability strictly greater than 1/2, the public coin model becomes trivial—every function can be computed with constant communication. In the unbounded-error private coin model, on the other hand, the inner product function still has complexity Ω(n) [For02].
41
ε+δ
this. A matching Ω(log n) lower bound is given by the following relation be- tween deterministic communication complexity and private coin randomized communication complexity.
Lemma 38 ([KN97]) For every function f : X × Y → {0, 1} Rpri (f ) ≥ Ω(log D(f )).
1/3
The proof of this lemma works by presenting a deterministic simulation of a
private coin randomized protocol.
4.1 Approximate rank
Our first lower bound technique for randomized communication complexity, as it was with deterministic communication complexity, will be based on matrix rank. For randomized complexity the relevant rank bound becomes approximate rank, which is the minimal rank of a matrix “close” to the target matrix.
Definition 39 (Approximate rank) Let A be a sign matrix. The approx- imate rank of A with approximation factor α, denoted rankα(A), is
rankα(A) = min rank(B). B:1≤A[i,j]B[i,j]≤α
Motivated by the limit as α → ∞, define
rank∞(A) = min rank(B).
B:1≤A[i,j]B[i,j]
This latter quantity is also known as the sign rank of A.
Note that approximate rank is defined as the optimum of an optimization problem. In practice, this optimum can be quite difficult to compute. While we do not know if computing approximate rank is NP-hard, the general class of problems of minimizing rank subject to linear constraints does contain NP-hard problems, see for example Section 7.3 of [VB96].
Krause [Kra96] showed that approximate rank can be used to lower bound randomized communication complexity.
Theorem 40 (Krause [Kra96]) Let A be a sign matrix and 0 ≤ ε < 1/2. Then
where α = 1/(1 − 2ε).
Rpri(A) ≥ log rankα(A) ε
42
Before we go into the proof, let us mention its application to the previ-
ous example of the equality function. Alon [Alo09] shows a bound on the
approximate rank of the identity matrix with approximation factor 2 of the
form rank2 (I2n ) = Ω(n). Combined with Theorem 40, this implies that
Rpri (I2n ) ≥ log n − O(1), giving an alternative proof of this lower bound. 1/4
Proof [Theorem 40] For this proof, it will be easier to work with Boolean matrices, thus let A0 = (J − A)/2 be the Boolean version of the sign matrix A, where J is the all-ones matrix. Consider an optimal private coin protocol P for A with success probability 1 − ε and communication complexity c. Let P be a matrix where
P[x,y] = Pr[P(x,y) = 1].
Notice that by assumption ∥A0 − P ∥∞ ≤ ε. We will now show that the rank of P is at most 2c. This will finish the proof by setting P∗ = −2P +J, that is by taking the inverse of the transformation from Boolean to sign matrices above.
As described above, we can represent a randomized protocol as a binary tree with internal nodes labeled by functions av : X × R → {0, 1} or bv : Y × R → {0,1}. Consider a leaf l in this tree, and let v1,...,vk,l be the path from the root v1 to l. We can alternatively indicate this path by labels s1 . . . sk ∈ {0, 1}k, specifying the values of avi or bvi . For the sake of notational simplicity we assume that Alice and Bob strictly alternate speaking on this path. On input x, y, we can write the probability that the protocol arrives at leaf l and outputs 1 as the product
Pr[av1(x,r) = s1]Pr[bv2(y,r) = s2]···Pr[avk(x,r) = sk]Pr[bl(y,r) = 1] rrrr
By grouping together the terms that depend on x and separately those that depend on y, we can write this more succinctly as Ul(x)Vl(y). Then we have
P [x, y] = Ul(x)Vl(y). l
Define the matrix U with rows labeled by elements from X and columns labeled by leaves l, and where U[x,l] = Ul(x). Define V similarly by V [y, l] = Vl(y). Now both U and V have at most 2c many columns and P = UV t. This demonstrates that rank(P) ≤ 2c.
By Newman’s theorem, we obtain the following corollary for public coin randomized complexity
43
Corollary 41 Let A be a 2n-by-2n sign matrix. For every ε, δ > 0 such that ε+δ<1/2setα=(1−2ε−2δ)−1. Then
Rε(A) ≥ log(rankα(A)) − O(log n − log δ).
In analogy with the log rank conjecture for deterministic complexity it is natural to conjecture that approximate rank similarly gives a polynomially tight lower bound on randomized complexity.
Conjecture 42 (log approximate rank conjecture) Fix 0 ≤ ε < 1/2. There is a constant c such that for every sign matrix A
Rpri(A) ≤ (log rankα(A))c + 2 ε
where α = 1/(1 − 2ε).
The limiting case as ε → 1/2 of this conjecture is true as Paturi and Si-
mon [PS86] show that log rank∞(A) characterizes the unbounded-error com-
plexity of A. In this model, the players simply have to output the cor-
rect answer with probability strictly greater than 1/2. On the other hand,
in the bounded-error case a larger gap is known here than for the deter-
ministic log rank conjecture—for the DISJOINTNESS problem on n bits
Rpri (DISJ) = Ω(n) [KS87] yet rank2(DISJ) = 2O(√n). The upper bound on 1/4
the approximate rank of DISJOINTNESS follows from an upper bound on quantum communication complexity [BCW98, AA05], see also Chapter 5.
The main drawback to the approximate rank technique is that in practice it can be very difficult to bound. One of the goals of the framework of approximate norms, discussed in Section 4.2, is to develop easier to compute convex relaxations of approximate rank.
4.2 Approximate norms
Like matrix rank for deterministic communication complexity, approximate rank is one of the strongest lower bound techniques available for randomized communication complexity. In Chapter 2 we saw several norms that can be used to lower bound matrix rank, for example γ2(·), μ(·), ∥ · ∥tr. We can naturally adapt these techniques to lower bound approximate rank by considering approximate norms.
44
Definition 43 (approximate norm) Fix a general norm Φ, which could be any of the above. For α ≥ 1 a real number and a sign matrix A, we define
Φα(A) = min Φ(B). B
1≤A[i,j]B[i,j]≤α Motivated by the limit as α → ∞ define
Φ∞(A) = min Φ(B). B
1≤A[i,j]B[i,j]
Note that an approximate norm is not in general itself a norm.
Recall Equation (2.1) which shows that for any real matrix A rank(A) ≥ max ∥A ◦ uvt∥2tr ,
This immediately implies that
α
rank (A) ≥
α2 ,
(4.1)
u,v
∥A ◦ uvt∥2F γ 2α ( A ) 2
as any matrix B that approximates the sign matrix A with factor α satisfies ∥B ◦ uvt∥2F ≤ α2, for arbitrary unit vectors u, v. The advantage of studying γ2α is that it is an optimization problem over a convex function, and it turns out that it can be computed with arbitrary accuracy in time polynomial in the size of the matrix by reduction to semidefinite programming.
As γ2α(A) provides a lower bound on approximate rank, Corollary 41 immediately implies that it, as well as μα(A) and ∥A∥αtr, can be used to lower bound randomized communication complexity.
The characterization of public coin randomized complexity as a proba- bility distribution over deterministic protocols (Theorem 36), however, leads to a much more natural proof based on convexity. We now give this proof which shows in general that for any norm Φ which gives a lower bound on deterministic communication complexity, the approximate norm Φα can be used to give a lower bound on randomized complexity.
Theorem 44 Let Φ be a norm. Suppose there is a constant c such that Φ(A) ≤ 2cD(A) for every sign matrix A. Then
cRε(A) ≥ log Φα(A) − log α, for every sign matrix A, where α = α(ε) = 1 .
45
1−2ε
Proof Sinceapubliccoinrandomizedcommunicationprotocolisequivalent to a probability distribution over deterministic protocols (Theorem 36), there aresignmatricesB1,...,Bm andaprobabilitydistributionp1,...,pm such that
1. ∥A − mi=1 piBi∥∞ ≤ 2ε.
2. D(Bi)≤Rε(A)for1≤i≤m.
Let B = 1 piBi. Chosen in this way, by item (1) we have that
1−2ε i
1 ≤ A[x, y]B[x, y] ≤ α for every entry (x, y). Therefore Φα(A) ≤ Φ(B)
by definition of an approximate norm. Since Φ is a norm we have 1
Φ(B) = Φ piBi 1−2ε i
≤ 1 piΦ(Bi) 1−2ε i
≤ 1 maxΦ(Bi). 1−2ε i
Combining this with our assumption that Φ(Bi) ≤ 2cD(Bi) and with item (2), we obtain Φ(B) ≤ 1 2cRε(A). This implies log Φα(A)−log α ≤ cRε(A).
As a corollary of this theorem, the approximate versions of the norms discussed in the chapter on deterministic complexity can all be used to lower bound randomized complexity. We just state this corollary for γ2, which dominates the trace norm method and μ norm, up to a constant factor.
Corollary 45 For every sign matrix A and 0 ≤ ε < 1 2
1−2ε
Rε(A) ≥ 2 log γ2α(A) − 2 log α, where α=α(ε)= 1 .
1−2ε
Proof Use the previous theorem together with the fact γ2(A) ≤ 2D(A)/2.
Up to an additive constant term, 2 log γ2α(A) gives tight bounds on the ran- domized communication complexity for almost every sign matrix [LMSS07]. Now γ2α is a convex relaxation of approximate rank which can be com- puted with high precision in polynomial time. The question remains: How much have we lost in considering this relaxation? Is there a sign matrix A
46
for which γ2α(A) can be much smaller than rankα(A)? The next theorem shows that, for constant α larger than 1, the answer is no.
Theorem 46 (Lee and Shraibman [LS08]) Let 1 < α < ∞. Then for any m-by-n sign matrix A
α α63 α6 rank (A)=O (α−1)6 ln (4mn)γ2(A) .
Before giving a proof sketch, let us make a few remarks. First, for the case α = ∞, Ben-David et al. [BES02] show the tighter result rank∞(A) = O(ln(4mn)γ2∞(A)2). The interesting thing is that in this case, the lower bound fails. Notice from Equation (4.1) that the lower bound deteriorates as α grows. Buhrman et al. [BVW07] and independently Sherstov [She08b] have shown that this is necessary, giving an example of a sign matrix A where γ2∞(A) is exponentially larger than rank∞(A).
Secondly, we mention that the logarithmic term in this theorem is nec- essary as demonstrated by the equality example studied earlier. Indeed, as log γ2α is a lower bound on public coin communication complexity, γ2α(I2n ) is constant while Alon shows that rankα(I2n) = Ω(n), for α = 2. This exam- ple also demonstrates that the assumption α > 1 cannot be removed, since rank(I2n ) = 2n.
Proof [sketch of Theorem 46] The proof combines two ideas. The first, observed by Alon and used by several authors [Alo03, AKM+06, KS07], is that approximate rank changes relatively slowly as a function of α, for α > 1. Quantitatively, one can show
rankα(A) ≤ 2(rank2α−1(A))3. This reduces the problem to showing
2α−1 α2 α2 rank (A) ≤ O (α − 1)2 ln(4mn)γ2 (A) .
For this part, we use dimension reduction. Notice that both matrix rank and γ2 are statements about matrix factorization. If a m-by-n matrix M has rank k, then there are vectors x1,…,xm ∈ Rk and y1,…,yn ∈ Rk such that M[i,j] = ⟨xi,yj⟩ for all 1 ≤ i ≤ m,1 ≤ j ≤ n. Similarly, if γ2(M) ≤ γ, then there are vectors x1,…,xm ∈ Rr and y1,…,yn ∈ Rr such that M[i,j] = ⟨xi,yj⟩ and ∥xi∥2,∥yj∥2 ≤ γ for every i,j. In other words, in the case of rank, we have a bound on the dimension of the vectors xi,yj, while in the case of γ2 we have a bound on their length. If the dimension r
47
is much larger than the length of these vectors, however, then intuitively it seems plausible that they can be compressed to a smaller dimension without affecting the inner products ⟨xi,yj⟩ too much. This intuition can be made precise by the Johnson-Lindenstrauss lemma [JL01]. We use a variant of this lemma from [BES02] which addresses exactly this situation.
Lemma 47 (Corollary 19, [BES02]) Let x,y ∈ Rr. Let R be a random k-by-r matrix with entries independent and identically distributed according to the normal distribution with mean 0 and variance 1. Then for every δ > 0
δ222
Pr |⟨Rx, Ry⟩ − ⟨x, y⟩| ≥ ∥x∥2 + ∥y∥2 ≤ 4 exp(−δ k/8).
Now let {xi},{yj} be a factorization which realizes γ2α(A) = γ. That is,
⟨xi,yj⟩ = B[i,j] where 1 ≤ A[i,j]B[i,j] ≤ α and ∥xi∥2,∥yj∥2 ≤ γ for all
R2
i,j. By taking k = 8(α−1γ)2 ln(8mn) we can ensure by a union bound that α α−1
|⟨Rxi,Ryj⟩ − ⟨xi,yj⟩| ≤ 2α simultaneously for all i,j with probability at least 1/2 over the choice of R. Setting x′ = α+1Rxi and y′ = α+1Ryj, the
i2α j2α
matrix whose (i, j) entry is ⟨x′i, yj′ ⟩ gives a 2α − 1 approximation to A and
has rank at most k.
4.3 Diagonal Fourier coefficients
We have just seen that the approximate norm γ2α is polynomially related to approximate rank, for constant α. This seems to indicate that one can generally show good lower bounds by this technique—indeed if the log ap- proximate rank conjecture is true, then one can always show polynomially tight lower bounds by studying γ2α.
More concretely, Linial and Shraibman [LS09c] show that the γ2α bound subsumes many other techniques in the literature. Here we see that γ2α gives bounds at least as large as those given by a technique based on diagonal Fourier coefficients, developed for randomized communication complexity by Raz [Raz95] and later extended to the quantum case by Klauck [Kla01].
We identify vectors in R2n with functions f : Zn2 → R. Similarly we identify real 2m × 2n matrices with functions A : Zm2 × Zn2 → R.
Corresponding to every z ∈ Zn2, is a character of Zn2 denoted χz. It is defined as
χz(x) = (−1)⟨z,x⟩, 48
for every x ∈ Zn2. The Fourier coefficients of a function f : Zn2 → R are fˆ= 1⟨f,χ⟩forallz∈Zn.ThecharactersofZm×Znaredenotedχ ′
z2nz 2 22 z,z for (z, z′) ∈ Zm2 × Zn2 . They satisfy
χz,z′ (x, y) = (−1)⟨z,x⟩+⟨z′,y⟩,
for every x ∈ Zm2 and y ∈ Zn2 . We denote by Bˆz,z′ the corresponding Fourier coefficient of a real matrix B.
Let A be a 2n × 2n sign matrix. The subject of this section is the sum of diagonal Fourier coefficients of A, i.e.
∥A∥D = |Aˆz,z|. z∈Zn2
By our notation one can get the impression that the sum of diagonal Fourier coefficients is a norm. It is actually not a norm, because it can achieve the value 0 on nonzero matrices. On the other hand, ∥ · ∥D satisfies all the other properties of a norm: nonnegativity, homogeneity, and subadditivity. A function that satisfy these properties is called a seminorm.
Raz [Raz95] derived the following lower bound in terms of diagonal Fourier coefficients.
Theorem 48 For every sign matrix A and ε < 1 2
Rε(A) ≥ log(∥A∥αD) − log α − O(1), where α=α(ε)= 1 .
1−2ε
The lower bound in Theorem 48 follows from Corollary 45 using the
following relation between γ2 and the sum of diagonal Fourier coefficients. Theorem 49 For every sign matrix A and α ≥ 1
γ 2α ( A ) ≥ 1 ∥ A ∥ αD . 2
We make use of the following simple fact:
Fact 50 Let z ∈ Zm2 and z′ ∈ Zn2 . The Fourier coefficient of the rank-one matrix fgt with respect to z,z′ is equal to fˆgˆ ′.
49
zz
Proof [of Theorem 49] Recall that γ2(M) ≥ 1ν(M) for every real matrix 2
M. We show next that ν(M) ≥ ∥M∥D. Combining these inequalities we get that γ2(M) ≥ 1∥M∥D for every real matrix M. The inequality between the
2
corresponding approximate norms then easily follows.
We turn to prove the inequality ν(M) ≥ ∥M∥D. Since the unit ball of
ν is the convex hull of rank-one sign matrices, it is enough to prove that for every rank-one sign matrix fgt it holds that ∥fgt∥D ≤ 1. This follows because if M = i βifigit and ν(M) = |βi|, then
∥M∥D =∥βifigit∥D ≤|βi|∥figit∥D ≤|βi|. iii
To prove that ∥fgt∥D ≤ 1 we use Fact 50. We get ∥fgt∥ =fˆgˆ
Dzz z
1/2 ˆ
1/2 gˆz2
The first inequality is an instance of the Cauchy-Schwarz inequality. The next identity holds because the characters form an orthogonal basis. The last equality uses the fact that f and g are sign vectors.
Remarks
1. The lower bounds proved in [Raz95, Kla01] in terms of diagonal Fourier coefficients, are different than what we have described above. But these bounds can be derived from the bounds we showed in terms of ∥ · ∥αD, using simple properties of approximate norms and error amplification for the randomized communication complexity, see e.g. [LS09c].
2. As observed by Raz, instead of diagonal Fourier coefficients one can consider other sets of Fourier coefficients. One can prove a similar statement (repeating the same arguments) for any subset F of Zn2 ×Zn2 of the form F = {(z,π(z)) : z ∈ Zn2}, where π is some permutation over Zn2 .
50
fz2 zz
≤
= 1 ∥f∥ 1 ∥g∥
2n/2 2 2n/2 2 = 1.
4.4 Distributional complexity and discrepancy
We turn to an alternative characterization of randomized complexity in terms of distributional complexity given by Yao [Yao83]. Distributional complexity considers deterministic algorithms, but allows them to answer incorrectly on some inputs (x,y). The requirement now is that the total measure of incorrect answers should be small, according to a probability distribution fixed in advance. This alternative characterization is very useful for proving lower bounds.
Recall that a public coin randomized protocol of complexity t is simply a probability distribution over deterministic protocols of cost at most t. This leads us to consider a geometric object, the convex hull of sign matrices with deterministic communication complexity at most t. Denote this convex body by B(D, t). A matrix B is in B(D, t) if and only if it can be written as the convex combination of sign matrices with deterministic communication complexity at most t. That is, if there is a probability distribution p1, . . . , pm and matrices B1,...,Bm such that D(Bi) ≤ t for i = 1...m and B = mi=1 piBi. Obviously,
B(D,1) ⊆ B(D,2) ⊆ B(D,3)...
As observed in Theorem 36, the randomized communication complexity Rε(A) is equal to the smallest number t such that A is 2ε close in l∞ distance to B(D,t). Formally, Rε(A) is equal to the minimal t such that
min ∥A−B∥∞ ≤2ε. B∈B(D,t)
This geometric definition shows that randomized complexity is an optimiza- tion problem over a convex set. As we shall see in Chapter 6 this allows the use of duality to obtain an equivalent characterization of randomized complexity in terms of a maximization problem. For the moment we simply state this result, and defer the proof to Section 6.2.1
Fix a distribution P on the entries of A. The distributional complexity of A with respect to P and ε, denoted DP,ε(A), is the minimal number t such that there exists a sign matrix B satisfying D(B) ≤ t and P ({(i, j) : A[i, j] ̸= B[i,j]}) ≤ ε. The distributional complexity of A with error parameter ε is defined
Dε(A) = max DP,ε(A). P
Using the von Neumann minimax theorem, Yao [Yao83] showed the fol- lowing.
51
Theorem 51 Let A be a sign matrix.
Rε(A) = Dε(A).
This theorem is the starting point for many lower bound proofs on random- ized complexity.
Discrepancy One early lower bound technique developed for showing lower bounds on randomized complexity based on Theorem 51 is the discrepancy method. This is a very general technique, which applies even as the error probability becomes very close to 1/2.
The discrepancy bound can be derived as follows. Let A be a sign ma- trix, and P a probability distribution over its entries. We think of P as a nonnegative matrix whose entries sum to one and which is of the same di- mensions as A. Let t = DP,ε(A) and let B be a sign matrix which “realizes” this—in other words B agrees with A with probability at least 1 − ε under the distribution P and D(B) = t. As A and B are different with probability at most ε with respect to P we have
⟨A ◦ P, B⟩ ≥ 1 − 2ε (4.2)
On the other hand, by Theorem 7, the matrix B can be partitioned into at most 2t monochromatic combinatorial rectangles {Rl}. Let c(Rl) ∈ {−1,+1} be the “color” of Rl. We can rewrite Equation (4.2) as
Denote
⟨A◦P,B⟩=c(Rl) A[i,j]P[i,j]
l (i,j )∈Rl
≤ A[i,j]P[i,j].
(4.3)
(4.4)
l (i,j )∈R
l
discP(A) = max A[i,j]P[i,j], R
(i,j )∈R
where the maximum is over all combinatorial rectangles. This is simply the cut norm of the matrix A ◦ P , so we can alternatively say discP (A) = μ∗ (A ◦ P ). It then follows from the Equations (4.2), (4.4) that 2t discP (A) ≥ 1 − 2ε, or equivalently
DP,ε(A)≥log 1−2ε . discP (A)
52
Let disc(A) = minP discP (A) be the discrepancy of A. As this derivation holds for an arbitrary probability distribution P we get
Theorem 52 (discrepancy method) For every sign matrix A and every 0 ≤ ε < 1/2
Rε(A)≥log 1−2ε. disc(A)
Before moving on, let us connect the discrepancy bound with the linear programming relaxation of nondeterministic communication complexity we saw in Chapter 3. Both disc(A) and C ̄1(A) are optimization problems over probability distributions. The dual formulation of C ̄1(A) can be expressed as
1 = minmaxP(R) = minmax A[i,j]P[i,j] C ̄ 1 (A) P R P R (i,j )∈R
where P is a probability distribution over {(i,j) : A[i,j] = 1} and R is a 1-monochromatic rectangle. On the other hand, in discrepancy the maxi- mization is over all rectangles. Thus as long as the optimal distribution in the discrepancy bound puts substantial weight on the set {(i, j) : A[i, j] = 1}, we will have C ̄1(A) = Ω(1/disc(A)). If the optimal distribution in the dis- crepancy bound does not put substantial weight on {(i, j) : A[i, j] = 1}, then the discrepancy method does not show a good lower bound anyway. This gives the following theorem.
Theorem 53 Let A be a sign matrix. Then
C ̄ 1 ( A ) ≥ 1 .
3 disc(A)
Proof Let P be a probability distribution such that disc(A) = discP (A). If P puts weight less than 1/3 on {(i, j) : A[i, j] = 1} then clearly disc(A) ≥ 1/3. Otherwise, there is a 1-monochromatic rectangle R such that 3P (R) ≥ 1/C ̄1(A). As disc(A) ≥ P(R), we get the theorem.
In particular, the discrepancy method also gives a lower bound on nondeter- ministic communication complexity.
4.5 Corruption bound
The last lower bound technique we discuss for randomized communication complexity is the corruption bound. This is a powerful lower bound technique
53
which is particularly interesting because for some functions it gives larger
lower bounds than approximate rank. Indeed, the corruption bound can be
used to show a tight Ω(n) lower bound on the complexity of DISJOINTNESS √
[Raz92a], while approximate rank can only show a lower bound of Θ( n). In particular, as the quantum communication complexity of DISJOINTNESS is
O(
lower bound techniques we know that can potentially separate quantum and randomized communication complexity for total functions. It is a major open question if these measures are polynomially related for all total functions. It is also an open problem whether the corruption bound and approximate rank are polynomially related.
The corruption bound does not really fall into the framework of lower bounds described in this survey. The definition of this bound is purely combinatorial, and it is not known if there is an equivalent definition which involves a representation of the function in Euclidean space. Still we feel it is insightful to describe this lower bound here and encourage further study of it and its relation with the other bounds in this survey.
The corruption bound was first introduced in a paper of Yao [Yao83], and was derived using the characterization of randomized complexity in terms of distributional complexity given in that same paper. Over the years, this technique has been variously called one-sided discrepancy, ε-error rectangle bound [Kla03], and corruption bound [BPSW06]. We will follow the latter terminology.
The original application of Yao gave the first explicit example of a func- tion whose randomized two-party complexity is Θ(n). Let p be an n-bit prime. The function he considered is f : Zp × Zp → Z2 defined as f (x, y) = ((x·y) modp) mod2.Inotherwords,f(x,y)istheparityof(x·y) modp. To prove a lower bound on this function, Yao proved the following general statement.
Letf:X×Y →Zbeafunctionandsay|X|=|Y|=N. Foreach x∈Xandz∈Z,denoteSx(z)={y:f(x,y)=z}. Wewritef−1(z)for the set of indices (x,y) for which f(x,y) = z.
Fixconstants0<μ<1/2and0<λ. Weneedthenotionsofmod- erate and anticorrelated. For z ∈ Z we say that f is z-moderate if μ < |f−1(z)|/N2 < 1 − μ. We say that f is z-anticorrelated if
|Sx(z)∩Sx′(z)|≤ 1|Sx(z)|·|Sx′(z)|(1+O( 1 )). N Nλ
√
n) [BCW98, AA05] the corruption bound is noteworthy as one of the few
foreveryx,x′ ∈X.
54
Theorem 54 (Yao [Yao83]) Let ε < 1/2 be a fixed constant. If f : X × Y → Z is both z-moderate and z-anticorrelated for some z ∈ Z, then Rε(f) = Θ(log N ), where |X | = |Y | = N .
The above lower bound is very elegant. It implies in particular that a pseu- dorandom sign matrix has high randomized communication complexity.
A key lemma in the proof of this theorem is the corruption bound tech- nique, which has since been used and reformulated by several authors [BFS86, Raz92a, Kla03, BPSW06]. Intuitively, the corruption bound interpolates be- tween the linear programming relaxation of nondeterministic communication complexity C ̄1(f) and the discrepancy method.
1 = min max A[i,j]P[i,j] C ̄1(A) P R:χ(R)=1 i,j∈R
disc(A) = min max A[i, j]P [i, j].
PR
i,j ∈R
In the first case, the probability distribution P is only over {(i, j) : A[i, j] = 1} and the maximization is over 1-monochromatic rectangles; in the second case the probability distribution is arbitrary but the maximization is over all rectangles. In the corruption bound, we minimize over probability distribu- tions that put sufficient weight on {(i,j) : A[i,j] = 1}, and maximize over rectangles that are nearly 1-monochromatic.
For a probability distribution μ and function f, say that a rectangle R is ε-monochromatic if μ(R ∩ f−1(0)) ≤ εμ(R). Further, let ε-monoμ(f) = max{μ(R) : R is ε-monochromatic} be the largest weight given to an ε- monochromatic rectangle under μ. The corruption bound gives the following.
Theorem 55 (corruption bound [Yao83, BPSW06]) Let B be a Boolean matrix and μ a probability distribution on the entries of B. Let ε′ > ε ≥ 0.
Then
⟨B,μ⟩−ε−ε/ε′ Rε(B) ≥ ε-monoμ(f) .
Proof We first use Yao’s principle that Rε(B) = Dε(B). Suppose that Dε(B) = c. Fix a distribution μ. Then here is a deterministic c-bit protocol P which errs on B with probability at most ε with respect to μ. Let {Ri} be a partition of B into 2c many rectangles given by this protocol, and let I be the set of indices i for which the protocol outputs 1 on Ri. Note that this partition satisfies the following two properties.
55
1. The probability with respect to μ that Ri contains a zero is at most ε: μ(Ri ∩f−1(0))≤ε.
i∈I
2. The rectangles Ri cover nearly all the ones of B, with respect to μ:
μ(Ri) ≥ ⟨B, μ⟩ − ε. i∈I
Setacut-offvalueε′ >ε. LetI′ ⊆Ibethesetofindicesofε′- monochromatic rectangles. By item (1), the total weight of rectangles which are not ε′-monochromatic is at most ε/ε′. We then have
μ(Ri) ≥ ⟨B, μ⟩ − ε − ε/ε′ i∈I ′
It is an open problem if the corruption bound is polynomially related to
randomized communication complexity (open problem 3.23 from [KN97]).
Klauck [Kla03] has shown interesting connections between the corruption
bound and the communication models corresponding to the complexity classes
MA and AM. He shows that the square root of the corruption bound is a
lower bound on MA complexity, thereby giving an Ω( n) lower bound on the MA complexity of disjointness. Surprisingly, this bound turns out to be tight by a beautiful protocol of Aaronson and Wigderson [AW09]. Klauck also shows that the corruption bound gives an upper bound on AM commu- nication complexity.
4.6 Summary
Complexity measures Let A be a sign matrix and let M be a real matrix
• Rε(A) – the randomized communication complexity of A with error
bound 0 ≤ ε < 1. 2
• rankα(A) - the approximate rank of A, with approximation factor α ≥ 1.
56
μ(Ri) ≤ 2c max ′′R
μ(R).
i∈I ε −monochromatic Rearranging gives the theorem.
√
• Dε(A) - the distributional complexity of A with error at most 0 ≤ ε < 1.
2
• disc(A) - the discrepancy of A.
• Φα(A) - the approximate Φ-norm of A, with approximation factor α ≥
1.
• ∥M∥D - the sum of diagonal Fourier coefficients of M.
Relations Let m ≤ n. For every m × n sign matrix A, a real matrix M and 0 ≤ ε < 1
2
• Rε(A) = Dε(A).
• Rε(A)≥log 1−2ε .
1−2ε
• rankα(A) ≥ γ2α(A)2 . α2
• rankα(A) = Oα ln3(4mn)γ2α(A)6, for every 1 < α < ∞. • γ2α(A) ≤ να(A) ≤ μα(A) ≤ 4KGγ2α(A).
• ν(M) ≥ ∥M∥D.
disc(A)
• Rε(A)≥2logγα(A)−2logα,whereα=α(ε)= 1 .
2 1−2ε
• Rε(A)≥logrankα(A)−O(logn),whereα=α(ε)= 1 .
57
Chapter 5
Quantum communication complexity
In this chapter, we look at lower bounds on quantum communication com- plexity. We will encounter familiar faces from the chapter on randomized communication complexity. Indeed, it is a major open question whether or not quantum communication complexity and randomized complexity are polynomially related for all total functions. For a partial function, however, an exponential separation between these models is known [Raz99].
A major obstacle to showing larger separations between these models for total functions—other than the fact that perhaps no such separation exists— is that nearly all lower bound techniques developed for the randomized model also work in the quantum model, even in the strongest quantum model where Alice and Bob share prior entanglement.
One outstanding exception to this is the corruption bound from Sec-
tion 4.5 which as mentioned can be used to show a lower bound of Ω(n) on
the randomized communication complexity of disjointness [KS87, Raz92b].
On the other hand, the quantum communication complexity of disjointness
√
is Θ(
is the largest gap known for a total function.
n) [Raz03, AA05], giving a quadratic gap between these models. This
5.1 Definition of the model
Intuitively, quantum communication complexity models are defined similarly to the corresponding classical ones, with qubits replacing classical bits. For- mally the protocols are described by unitary transformations operating on vectors in a Hilbert space. The state of a quantum communication protocol
58
is represented as vector in a Hilbert space HA ⊗ C ⊗ HB. Here HA,HB are Hilbert spaces of arbitrary finite dimension representing the “workspace” of Alice and Bob respectively. The Hilbert space C is 2-dimensional and it stands for a one-qubit channel. We assume that HA and HB each con- tain a register to hold the input. Thus we have HA = HIA ⊗ HWA and HB = HIB ⊗ HWB where HI is a register and HW represents workspace that is used arbitrarily.
In the model without entanglement, the initial state of a quantum pro- tocol on input (x,y) is the vector |Ψ0x,y⟩ = |x,0⟩|0⟩|y,0⟩, where in each case |0⟩ is an arbitrary unit vector independent of the input. Thus informally, the workspaces and channel are initially “clear.”
With entanglement, the initial state is a unit vector of the form |Ψ0x,y⟩ = w αw|x, w⟩|0⟩|y, w⟩, where the coefficients αw are arbitrary real numbers satisfying w αw2 = 1. This difference in allowed initial state is the only change between the models with and without entanglement.
Unlike other models of communication, here we assume that the speaking order of the players strictly alternates 1. Alice and Bob “speak” by applying a unitary transformation to the current state of the protocol. On Alice’s turn, she applies an arbitrary unitary transformation of the form U ⊗ IB which acts as the identity on HB. Similarly, on a turn of Bob he applies a transformation of the form IA ⊗ U which acts as the identity on HA. Thus after 2t rounds, the state of the protocol is
|Ψ2t ⟩=(I ⊗U )···(I ⊗U )(U ⊗I )|Ψ0 ⟩ x,y A 2t A 2 1 B x,y
At the end of a t-round protocol, we project the final state |Ψtx,y⟩ onto the subspace HA ⊗ |1⟩ ⊗ HB. Denoting the length of this projection by p, the protocol outputs 1 with probability p2, and outputs 0 otherwise. As the state of a quantum protocol is a unit vector, this is equivalent to outputting 0 with probability the norm squared of the projection of the final state onto HA ⊗ |0⟩ ⊗ HB. A quantum protocol computes a Boolean matrix B with probability at least 1 − ε, if its output is in {0, 1} and the output is equal to B[x, y] with probability at least 1 − ε for every input (x, y). The cost of a protocol is simply the number of rounds. We define the quantum communication complexity Qε(B) of a Boolean matrix B, to be the minimal cost of a quantum protocol for B which succeeds with probability at least 1 − ε in the model without entanglement. We define Q∗ε(B) similarly for the model with entanglement. We will also refer to these measures for a sign
1Note that this requirement makes a difference of at most a multiplicative factor of two in the communication complexity.
59
matrix A by the usual identification with the Boolean matrix B = (A−J)/2, where J is the all-ones matrix.
5.2 Approximate rank
As we have already been accustomed, we begin with a lower bound based on matrix rank. Buhrman and de Wolf [BW01] showed that approximate rank provides a lower bound on quantum communication without entanglement.
Theorem 56 (Buhrman and de Wolf [BW01]) Let A be a sign matrix, and 0≤ε<1/2, then
Qε(A) ≥ log rankα(A), 2
where α = 1/(1 − 2ε).
Notice that this bound is the same as the approximate rank bound for private coin randomized protocols, up to the factor of two. Similarly to public coin randomized protocols, this bound does not hold as is for the model of quantum communication with entanglement—with entanglement Alice and Bob can simulate a public coin.
Instead of proving Theorem 56, in the next section we prove a lower bound on quantum communication complexity with entanglement in terms of γ2α. As γ2α and approximate rank are polynomially related Theorem 46, this implies that the logarithm of approximate rank also lower bounds this model, up to a slightly larger multiplicative factor and logarithmic fudge terms.
Where there is a rank bound, so goes a log rank conjecture. The quantum model is no exception.
Conjecture 57 (log rank conjecture, quantum version) Fix 0 ≤ ε < 1/2. There is a constant c such that for every sign matrix A
Qε(A) ≤ (log rankα(A))c + 2,
In our opinion, the quantum version of the log rank conjecture is the most
where α = 1/(1 − 2ε).
plausible of them all. Indeed, here we are not aware of any example where
60
quantum communication complexity is significantly larger than the loga- rithm of approximate rank.
Question 58 Give an example of a sign matrix A such that Q1/3(A) ≥ (log rank2(A))c + 2
for a constant c > 1.
5.3 A lower bound via γ2α
As approximate rank is a lower bound on quantum communication complex- ity, all the methods subsumed by the approximate rank technique will also lower bound quantum complexity. In particular, the approximate norm γ2α can be used to lower bound quantum communication complexity. We present a separate proof for this fact however, which gives a sharper bound and also works in the stronger model with entanglement.
Previously, we proved lower bounds on communication complexity by identifying a set of “simple” objects and seeing how a correct protocol de- composes the communication matrix as a linear combination of these simple objects. For example, in the case of deterministic protocols these simpler objects were combinatorial rectangles, or equivalently rank-one Boolean ma- trices. The μ norm measures the lowest “weight” decomposition of a matrix as a linear combination of combinatorial rectangles.
Combinatorial rectangles came up naturally in the context of deter- ministic communication protocols, as the latter partition the matrix into monochromatic combinatorial rectangles. This property is not shared by quantum communication protocols in any apparent way. Remarkably, an ef- ficient quantum protocol still leads to an efficient (approximate) description of the underlying matrix in terms of rank-one Boolean matrices, just as in the randomized case. This fact was first observed by Klauck [Kla01] who showed that Qε(A) = Ω(log μα(A)).
Klauck’s work builds on earlier work of Yao and Kremer [Yao93, Kre95] which began to formalize the mathematical properties of a sign matrix with small bounded-error quantum communication complexity. We present here what is currently the sharpest analysis of this form, which is in terms of the γ2 norm due to Linial and Shraibman [LS09c]. Roughly speaking, this result says that if a sign matrix A has bounded-error quantum communication complexity c, even in the model with entanglement, then there is a matrix B close to A which satisfies γ2(B) ≤ 2c. The relation to combinatorial
61
rectangles is then nicely explained by Grothendieck’s inequality which says that γ2 and μ are closely related (See also Section 2.3).
The proof of Linial and Shraibman proceeds by explicitly constructing a factorization to imply that γ2 is small. For variety, we present here a different proof of this result communicated to us by Harry Buhrman [Buh07] that proceeds via the dual norm of γ2 and exploits the connection of γ2∗ with so- called XOR games. A similar approach is used by Degorre et al. [DKLR08] to show a lower bound not just on functions, but also on the complexity of simulating probability distributions. To explain this approach, let us first introduce XOR games.
5.3.1 XOR games
A XOR game is played by three parties, provers Alice and Bob and a verifier V. Let A be a |X|-by-|Y | sign matrix for two finite sets X, Y . The verifier chooses (x, y) ∈ X ×Y according to some probability distribution π(x, y) and sends x to Alice and y to Bob. The provers then answer by ax, by ∈ {−1, +1} with the goal that ax · by = A[x, y]. In other words, the provers want the XOR of their answers to agree with A, explaining the name “XOR game.” The provers are allowed to have access to a shared random string, but a convexity argument shows that they can perform as well without it.
We will be interested in the maximal correlation the provers are able to achieve with A under the distribution π. By definition, this is the probability that the provers answer correctly minus the probability that they answer incorrectly. One can see that this is exactly given by
Corrπ(A,P)= max A[x,y]π(x,y)ax ·by a∈{−1,+1}|X | x,y
b∈{−1,+1}|Y |
= max aT(A◦π)b. a∈{−1,+1}|X |
b∈{−1,+1}|Y |
This last quantity is exactly the infinity-to-one norm introduced in Sec- tion 2.3.5. Thus we can equivalently say
Corrπ(A,P) = ∥A◦π∥∞→1.
We have just described a classical XOR game. We will actually be in- terested in the case where Alice and Bob share entanglement. Formally, a XOR protocol with entanglement is described by a shared quantum state
62
|ψ⟩ ∈ Cd×d for some d ≥ 1 and a choice of ±1 valued measurement observ- ables Ax for every x ∈ X and similarly By for every y ∈ Y . On input (x, y) the protocol outputs 1 with probability
⟨ψ|Ax ⊗ By|ψ⟩.
Thus for a protocol P with shared entanglement and sign matrix A we have
Corrπ(A,P)=A[x,y]π(x,y)·⟨ψ|Ax ⊗By|ψ⟩. x,y
Tsirelson [Tsi87] has given a very elegant characterization of the maximal correlation achievable by the provers in this situation.
Theorem 59 (Tsirelson [Tsi87]) Let A be a sign matrix. For any proba- bility distribution π over A
maxCorrπ(A,P) = γ2∗(A◦π). P
where the maximum is taken over XOR protocols P with shared entanglement.
A very accessible presentation of this result can be found in the appendix of Unger’s thesis [Ung08]. Note that as the maximization in the definition of γ2∗ is over a larger set than that of ∥A∥∞→1 we have ∥A ◦ π∥∞→1 ≤ γ2∗(A ◦ π). The famous CHSH game [CHSH69] is a simple XOR game where provers sharing entanglement can do better than those without, under the uniform distribution. The CHSH game is described by the matrix
1 1 CHSH= 1 −1 .
As this matrix represents the truth table of the AND function (where −1 represents true), in words the goal of the provers in a CHSH game on input x,yistooutputa,bsuchthata⊕b=x∧y. Itisnotdifficulttoshowthat 1/2 = (1/4)∥CHSH∥∞→1 < (1/4)γ2∗(CHSH) = 1/√2, thus provers sharing entanglement can achieve strictly better correlation in the CHSH game under the uniform distribution.
The gap between ∥A ◦ π∥∞→1 and γ2∗(A ◦ π) cannot be much larger.
Grothendieck’s inequality (Theorem 26) ensures that γ2∗(M) ≤ KG∥M∥∞→1
for every real matrix M, where KG ≤ 1.78... is Grothendieck’s constant.
Thus the optimal.
√
2 gap exhibited by the CHSH game example is not far from
63
5.3.2 A communication protocol gives a XOR protocol
As observed by Harry Buhrman, Theorem 59 can be used to give an alter- native proof of a result of Linial and Shraibman. See also [DKLR08] for a proof of a more general result along similar lines.
Theorem 60 (Linial and Shraibman [LS09c]) Let A be a sign matrix and 0≤ε<1/2, then
2Q∗ε (A) ≥ (1 − 2ε) · γ1/(1−2ε)(A) 2
= max (1 − ε)⟨A, M ⟩ − ε∥M ∥1 . M γ 2∗ ( M )
The equality here follows by duality as proved in 6.2.2.
Buhrman’s proof actually gives a slightly weaker bound
22Q∗ε(A) ≥max⟨A,M⟩−2ε∥M∥1. M γ 2∗ ( M )
(5.1)
The better bound in Theorem 60 makes use of the assumption that the players strictly alternate in speaking order, which the proof given here does not. For comparison, recall that we know that the square of the right hand side in Theorem 60 is a lower bound on 2Rε(A).
Proof [of inequality (5.1)] Say that Q∗ε(A) = c. By using teleportation two players who share entanglement can encode a quantum bit with two classical bits. We refer the reader to the textbook of Nielsen and Chuang for details [NC00]. This allows the transformation of the original protocol into one with the same properties using at most 2c classical bits. Let R[x, y] denote the expectation of the output of this protocol on input x,y. Note that, by assumption of the correctness of the protocol, if A[x,y] = 1 then 1 − 2ε ≤ R[x, y] ≤ 1 and if A[x, y] = −1 then −1 ≤ R[x, y] ≤ −1 + 2ε.
Fix a probability distribution π and let B be an arbitrary sign matrix of the same dimensions as A. We will see how the communication protocol for A can be used to design a XOR protocol for B. The bias of this protocol will be related to the amount of communication c and the correlation ⟨A, B ◦ π⟩.
The strategy in the XOR game is as follows: As the provers share en- tanglement, we may also assume they share a random string r of length 2c. Essentially, the players will simulate their actions in the communication protocol but instead of actually communicating will take the responses from the other player to be given by r. More explicitly, say that Alice speaks first in the communication protocol—she makes a measurement on the entangled
64
state and communicates a t-bit string b to Bob. In the XOR protocol, she does the exact same thing but instead of sending the message to Bob, she checks that what she would send agrees with the first t bits of r. If at any point in the protocol r does not agree with the communication Alice would have sent, we say that r is inconsistent with Alice. Similarly, Bob treats the first t bits of r as if this was the message he received from Alice, and performs the same action he would then do in the communication protocol. If Bob ever sees that r does not agree with the message he would send in the communication protocol, we say that r is inconsistent with Bob.
Now we define the output conditions
• If the random string r is inconsistent with Alice, then she outputs a random bit in {−1, +1}. Otherwise, she outputs a bit {−1, +1} with expectation R[x, y].
• If r is inconsistent with Bob, then he outputs a random bit. Otherwise, he outputs 1.
Let P (x, y) be the expected output of this protocol on input x, y. Let us now compute the correlation of this protocol with B under π:
γ2∗(B ◦ π) ≥ Corrπ(B,P)
=
≥
1 π(x, y)B[x, y]R[x, y]
1
π(x, y)B[x, y]A[x, y] − 2ε x,y
22c
Rearranging, this gives the desired result:
22c
x,y
22c ≥max⟨A,B◦π⟩−2ε =max⟨A,M⟩−2ε∥M∥1 B,π γ2∗(B ◦ π) M γ2∗(M)
5.4 Summary: equivalent representations
Recall that this survey revolves around a “three-step approach.” We focus on lower bounds that generally speaking follow the three steps
1. Finding a representation.
65
2. Quantifier switching.
3. Finding a witness.
The previous chapters were mainly concerned with the first step of find- ing a representation of the communication complexity measure in Euclidean space. We have seen various representations for several communication com- plexity measures, e.g. rank, approximate rank, and approximate norms. Different communication complexity measures give rise to different repre- sentations, reflecting their nature. For example, many representations for randomized complexity were simply “approximate” versions of determinis- tic complexity measures. These approximate versions, such as rankα and γ2α, tend to be fairly robust in the variation of α > 1, just as randomized complexity itself is robust in the allowable error parameter ε. On the other hand, rank(A) and rankα(A) for α > 1 can be vastly different, as can D(f) and Rε(f) In this way, the difference between deterministic and randomized complexity is well expressed by their representations.
One might expect to similarly see a difference in the representations for randomized and quantum communication complexity. The surprising result of this section is that this is not the case. Natural representations for ran- domized communication complexity, like approximate rank and approximate norms such as μα turn out to also be representations for quantum communi- cation complexity. Thus, at least when considering this approach, we cannot distinguish between classical and quantum complexities after the first step of the three-step approach.
We again stress that there are randomized lower bound techniques, such as the corruption bound and information theoretic techniques, which do not always give lower bounds on quantum communication complexity. These bounds, however, are more combinatorial and less geometrical. It seems a difficult task to find other representations which distinguish between ran- domized and quantum communication complexity. We refer the reader to [LS09c, LSS09] for further reading on the equivalence between the natural representations for randomized and quantum communication complexity in different models.
66
Chapter 6
The role of duality in proving lower bounds
This chapter deals with the second step of our three-step approach, that is quantifier-switching. This is, of course, a very broad subject, and we only discuss one generic tool to address this problem, duality. We consider principles of duality and study their close relation to quantifier switching. Recall that at this point, step 2 of the three-step approach, we have some complexity measure G which is phrased in terms of a minimization, e.g. an approximate norm. Duality provides a means to obtain an equivalent formulation of G in terms of a maximization.
Finding a dual formulation (in terms of a maximization) is the subject of Section 6.2. The preliminary Section 6.1 details the exact principles of duality that we need, including basic definitions and the statement of the separation theorem.
Although our main focus is in communication complexity, we take the opportunity in this section to discuss duality and its application in a broader context.
6.1 Duality and the separation theorem
Duality has a large number of meanings in mathematics. It appears in many areas e.g. linear algebra, geometry, group theory, graph theory, logic and order theory. Even if we restrict ourselves to the area we are considering, i.e. geometry, we are still left with many different notions. Examples of such notions of duality are linear programming and semidefinite programming duality, the dual space (of linear functionals), norms duality and a list of
67
duality transforms.
The notion of duality we have in mind is the linear algebraic duality
between a vector space and the space of linear functionals operating on that space. This notion of duality is related to other notions such as a dual norm and the duality transform. These concepts are discussed in more detail in Section 6.1.1.
The following theorem (and similar theorems) is the main engine behind the use of duality for quantifier-switching.
Theorem 61 (Separation theorem) Let X1 and X2 be convex subsets of Rn. IfX1∩X2 =∅thenthereisavectory̸=0andascalarbsuchthat
1. ⟨x,y⟩≤b for all x∈X1,
2. ⟨x,y⟩≥b for all x∈X2.
If X1 and X2 are closed and at least one of them is bounded, then the sepa-
ration above can be made strict.
An equivalent way to state Theorem 61 is: Given two convex subsets X1 and X2 of Rn, if X1 and X2 are disjoint then there exists an affine hyperplane H such that X1 is contained in the half-space on one side of H and X2 is contained in the complementing half-space (i.e., H separates X1 from X2).
Note that the assumption X1 ∩ X2 = ∅ in Theorem 61 is about nonex- istence (of a point in both X1 and X2), while the consequence is about existence (of a separating hyperplane). This way the separation theorem, when applicable, provides a way to transform a statement about nonexis- tence into a statement about existence. In particular Theorem 61 provides a tool to switch a universal quantifier with an existential quantifier, which is what we need.
Illustrative examples of how Theorem 61 is used for switching quantifiers in the context of communication complexity are provided in Section 6.2. We prove there the equivalence between randomized communication complexity and distributional complexity, and also provide an equivalent formulation for approximate norms.
6.1.1 Dual space, dual norms and the duality transform
The aim of this section is to introduce the notions of a dual space, dual norm and the duality transform. We also study basic properties of these definitions and examine them from a complexity theoretic point of view.
68
We start with the dual space of linear functionals. Given a vector space V over a field F, the set of all linear functionals form V to F is called the dual space. When the vector space is Rn, the dual space is also isomorphic to Rn. A natural isomorphism maps a vector y ∈ Rn to the linear functional f : Rn → R defined by f(x) = ⟨y,x⟩.
Observe that the consequence in Theorem 61 is really a statement about the dual space, its subject is a separating hyperplane or equivalently a linear functional. Therefore duality is inherent in any application of the separation theorem.
Banach space theory studies vector spaces equipped with a norm. For example the space ln2 = (Rn,∥·∥2) is the vector space Rn with the l2 (Frobe- nius) norm. Now the dual space of linear operators is also a Banach space (with a norm defined on it). The dual space of a Banach space (V, ∥ · ∥) is the pair (V ∗, ∥ · ∥∗). Here V ∗ is the dual space of linear functionals and ∥ · ∥∗ is the dual norm, defined for every f ∈ V ∗ by
∥f∥∗ = max f(x). x∈V :∥x∥≤1
In words, the dual norm of f is the maximal value given by f to a vector with unit norm. In the special case V = Rn we are interested in, this takes the form
∥y∥∗ = max ⟨y,x⟩. x∈Rn :∥x∥≤1
for every y ∈ Rn.
Another, more combinatorial way, to reach the definition of a dual norm
is as follows: It starts with the (geometric) duality transform. To a nonzero point a ∈ Rn\{0} the duality transform assigns the hyperplane {x ∈ Rn : ⟨a, x⟩ = 1}, and to a hyperplane H that does not pass trough the origin and can be uniquely written as H = {x ∈ Rn : ⟨a,x⟩ = 1} it assigns the point a.
From the duality transform that assigns hyperplanes to points and vice versa, one can derive a transformation on sets of points. For a set X ⊂ Rn we define the set dual to X, denoted by X∗, as follows:
In other words
X∗ ={y∈Rn :⟨x,y⟩≤1forallx∈X}. X∗ ={y∈Rn :sup⟨x,y⟩≤1}.
x∈X
A simple, but important, property of dual sets is
Fact62 ForanysetX⊂Rn
1. The set X∗ is closed and convex and contains the origin.
69
2. The set (X∗)∗ is the closure of conv(X ∪ {0}).
The first part of Fact 62 is easy, and the second is proved using Theorem 61. It follows that for every closed and convex set X ⊂ Rn that contains the origin we have that (X∗)∗ = X.
Convexity is a prerequisite for Theorem 61 to apply. Without the as- sumption that X1 and X2 are convex the statement of this theorem is false. This is one reason why working with norms is very convenient. We describe norms and duality of norms in a little more detail next.
Norms
AnormonRn isafunctionΦ:Rn →Rsuchthat 1. Φ(x) > 0 for every x ∈ Rn\{0}.
2. Φ(a·x)=|a|Φ(x)foreveryx∈Rn anda∈R. 3. Φ(x+y)≤Φ(x)+Φ(y)foreveryx,y∈Rn.
LetΦbeanormonRn,thesetBΦ ={x∈Rn :Φ(x)≤1}iscalled the unit ball of Φ. It is not hard to verify that BΦ is convex and symmetric around the origin. On the other hand, given a convex and 0-symmetric body B ⊂ Rn, it naturally induces a norm ΦB by the Minkowski functional. Namely, ΦB(x) is equal to c−1, where c is the minimal scalar such that c · x ∈ B. Norms can therefore be identified with their unit balls.
Consider BΦ∗ , the dual set to BΦ. We have that BΦ∗={y∈Rn: sup⟨x,y⟩≤1}.
x:Φ(x)≤1
Therefore, for every pair of vectors x ∈ Rn and y ∈ BΦ∗
⟨x, y⟩ ≤ Φ(x).
This inequality is sometimes called weak duality. The separation theorem implies that strong duality also holds, i.e. that for every x ∈ Rn there is a y ∈ BΦ∗ such that ⟨x, y⟩ = Φ(x). Observe that BΦ∗ = BΦ∗ , i.e. the dual norm Φ∗ is the norm induced by the dual set BΦ∗ .
Duality, combined with the separation theorem thus provides an equiva- lent formulation of any norm Φ in terms of a maximization:
Φ(x) = max |⟨x, y⟩|. (6.1) y:Φ∗(y)≤1
70
Let us now interpret this from a complexity theoretic point of view, which is our main objective. Assume we have a vector x for which we want to prove that Φ(x) is large. Any vector y ∈ BΦ∗ provides a proof of some lower bound on Φ(x), and strong duality implies that this proof system is optimal, i.e. there is always a proof of this type that gives the value of Φ(x).
6.2 Applying the separation theorem – finding a dual formulation
6.2.1 Distributional complexity
The next theorem is the equivalence between randomized communication complexity and distributional complexity, proved by Yao [Yao83, KN97] us- ing a minimax theorem. We apply Theorem 61 directly to prove this equiv- alence.
Theorem 63 For every sign matrix A, Rε(A) is equal to
max min D(B), PB
P (B[i,j]̸=A[i,j])≤ε
where the maximum is over all probability distributions P on the entries of
A, and B ranges over sign matrices.
Proof Recall from Section 4.4 that for a sign matrix A, Rε(A) is the minimal number t such that there exists a matrix E ̃ ∈ B(D,t) satisfying ∥ A − E ̃ ∥ ∞ ≤ 2 ε .
First let us see that Rε(A) is larger than the expression in the theorem (i.e., distributional complexity of A). Say Rε(A) = t and assume
∥A−pkEk∥∞ ≤2ε, k
where p1, . . . , pm are a probability distribution and E1, . . . , Em are sign ma- trices with deterministic communication complexity at most t. For every matrixY with∥Y∥1 =1wehave
Y [i, j](A[i, j] − pkEk[i, j]) ≤ 2ε. i,j k
Rearranging, we get
p Y[i,j](A[i,j]−E [i,j])≤2ε. kk
k i,j
71
Therefore there is some k ∈ [m] such that
Y [i, j](A[i, j] − Ek[i, j]) ≤ 2ε
i,j
Considering matrices Y of the form Y = A◦P for an arbitrary probability dis- tribution P we can reinterpret the above inequality as P(A[i,j] ̸= Ek[i,j]) ≤ ε. Since we work with an arbitrary distribution P, and D(Ek) ≤ t, we get that the distributional complexity of A is smaller than Rε(A).
For the opposite inequality, fix a number t and assume that Rε(A) > t. Denote by Aε the following set
Aε ={A ̃:∥A−A ̃∥∞ ≤2ε}={A+∆:∥∆∥∞ ≤2ε}.
Both B(D, t) and Aε are closed and bounded convex sets, and our assumption that Rε > t implies that they are disjoint. By Theorem 61 therefore, there is a matrix Y and a scalar b such that
1. ⟨E ̃,Y⟩≤bforallE ̃∈B(D,t),
2. ⟨A ̃,Y⟩>bforallA ̃∈Aε.
It is not hard to check that the above two conditions are equivalent to:
1. ⟨E,Y⟩≤bforallEwithD(E)≤t,
2. ⟨A+∆,Y⟩>bforall∆satisfying∥∆∥∞ ≤2ε.
We can assume without loss of generality that ∥Y ∥1 = 1. Let S = sign(Y ) be the sign matrix whose (i, j) entry is the sign of Y [i, j], and denote P = S ◦ Y . Observe that P is a probability distribution. We can rewrite our two conditions as
1. ⟨E◦S,P⟩≤bforallEwithD(E)≤t,
2. ⟨(A+∆)◦S,P⟩>bforall∆satisfying∥∆∥∞ ≤2ε.
By choosing ∆ = −2εS in the second condition we get that ⟨A◦S, P ⟩ > b+2ε, which together with the first condition implies that the probability with re- spect to P that A is different from E is larger than ε for every sign matrix E with D(E) ≤ t. The distributional complexity of A is therefore also larger than t, concluding the proof.
72
6.2.2 Approximate norms
We have defined approximate norms in Section 4.2, to serve as a representing measure for randomized communication complexity in different models. In this section we apply duality to find an equivalent formulation for approxi- mate norms.
As it will require no additional effort in the proof, we consider the follow- ing slightly more general definition of an approximate norm. Let Φ and ξ be two norms on Rn and let α ≥ 1 be a real number. The (α, Φ, ξ)-approximate norm is defined by
Φαξ (x) = min Φ(y) y:ξ(y− 1+α x)≤ α−1
for every x ∈ {±1}n. Using duality we get
Theorem64 ForanytwonormsΦandξonRn,arealnumberα≥1,and
every x ∈ {±1}n
Φαξ(x)= max (1+α)⟨x,w⟩+(1−α)ξ∗(w)
Proof Fix a sign vector x ∈ {±1}n, and let t be a real number such that Φαξ (x) > t. Consider the following two convex sets
22
∗w22 Φ (w)≤1
and
1+α α−1 Y= y|ξ(y− 2 x)≤ 2
Z = {z|Φ(z) ≤ t}.
Y and Z are closed, convex, and bounded subsets of Rn. Our assumption that Φαξ (x) > t implies that Y ∩Z = ∅. By the separation theorem therefore, there is a vector w and a scalar b such that
1. ⟨w,y⟩>bforally∈Y, 2. ⟨w,z⟩≤bforallz∈Z.
Note that Z = t · BΦ and hence, the second condition is equivalent to saying that Φ(w)∗ ≤ b/t. As for the first condition, observe that one can
rewrite Y as
1+α α−1 Y= 2x+∆|ξ(∆)≤2
73
Rewriting the first condition accordingly we get that
1 + α ⟨w, x⟩ − max⟨w, ∆⟩ > b, (6.2)
2∆
where the maximum is over all ∆ such that ξ(∆) ≤ (α − 1)/2. By the definition of a dual norm the maximum in Equation (6.2) is equal to (α − 1)ξ∗(w)/2. We conclude then that there exists a vector w such that Φ∗(w) ≤ b/t and
1+α⟨w,x⟩+ 1−αξ∗(w) > b. 22
Normalizing w so that Φ∗(w) ≤ 1 we get that the expression in the theorem is at least as large as Φαξ (x). It is not hard to verify that the converse in- equality is also true, which concludes the theorem.
Comparing the dual expression for norms and approximate norms we see that for approximate norms the functional we are optimizing on is more cumbersome, involving ξ∗(w) and not only the inner product we had before, and a weighting that depends on α. Nevertheless the set of witnesses we need to consider, i.e. BΦ∗, remains the same. The problems of finding a good witness for some norm or any approximate version of it share much in common.
74
Chapter 7
Choosing a witness
We have now seen several examples of approximate norms and how they can give lower bounds on communication complexity. We have also seen how approximate norms have an equivalent formulation in terms of a maximiza- tion problem. We are left with the third step of the three-step approach, the problem of finding a good witness. In this section we focus on this problem for approximate norms where ξ = l∞. Recall from Theorem 64 that the equivalent maximization formulation for an approximate norm in this case is
Φα(x)= max (1+α)⟨x,w⟩+(1−α)∥w∥1. w:Φ∗(w)≤1 2 2
Thus, we need to find a vector w satisfying Φ∗(w) ≤ 1 for which the target function is large. This problem can be quite difficult to solve in general; we will restrict ourselves to two specific known cases: a general heuristic for choosing w as a weighted version of x, described in Section 7.1, and a family of structured vectors x for which we know how to optimally choose w, described in Section 7.2.
7.1 Nonnegative weighting
For a given sign vector x ∈ {±1}N we seek a vector w that maximizes
max (1 + α)⟨x, w⟩ + (1 − α)∥w∥1 . (7.1)
w 2Φ∗(w)
A first choice that comes to mind is to take w = x. Since x ∈ {±1}N this gives
Φα(x)≥ N . (7.2) Φ∗ (x)
75
The quality of this lower bound depends on the value of Φ∗(x). Sometimes this simple choice provides a tight lower bound for Φα(x), as illustrated by the next example.
Example 65 Consider real 2n-by-2n matrices with the trace norm ∥ · ∥tr. The operator norm, or spectral norm, ∥ · ∥, is dual to the trace norm.
Recall from Theorem 18 that for a 2n-by-2n sign matrix A 2D(A) ≥ ∥A∥2tr .
22n
As D(A) ≤ n + 1, this shows that ∥A∥tr ≤ 2(3n+1)/2. It follows that
∥A∥αtr ≤ ∥A∥tr ≤ 2(3n+1)/2,
for every 2n × 2n sign matrix A and every real number α ≥ 1.
Taking A to be the Hadamard matrix Hn, we see that this upper bound can be tight. Simply take the witness w to be Hn as well. As HnHnt = 2nI
we have ∥Hn∥ = 2n/2, and so by Equation (7.2), α 22n 3n/2
∥Hn∥tr ≥ ∥Hn∥ = 2 .
In communication complexity terms, by Corollary 45 this means that the
inner product function on n bits has randomized communication complexity
n−O(logn) bits even when the allowed error is ε= 1 − 1 . 2 nO(1)
The above example shows that x itself can sometimes be a good witness. But this is not always so:
Example 66 Consider the settings of Example 65. Denote by Jn the 2n × 2n sign matrix all of whose elements are 1, and Hn is again the Hadamard matrix of the same size. Take the matrix
Hn−1 Jn−1 A = Jn−1 Jn−1
The approximate trace norm of a sign matrix is at least the approximate trace norm of any of its submatrices, thus by the previous example
∥A∥αtr ≥ 23(n−1)/2
On the other hand, the operator norm of A is larger than 2n . Therefore,
√
2
taking A itself as a witness only gives ∥A∥tr ≥ 2n+1/2, which leads to a trivial
communication complexity bound.
76
A natural remedy to overcome the pitfalls of the previous example is to choose a witness of the form w = p ◦ x where p is a probability vector (i.e., a nonnegative vector whose entries sum up to 1). The numerator of Equation (7.1) is still easy to handle, and we get
Φα(x)≥ max 1 . (7.3) p:p≥0 Φ∗(p ◦ x)
∥p∥1 =1
Note that taking w = x is equivalent to taking p above to be the uniform probability distribution.
Taking a weighted version of x can improve the lower bounds we can get. For example, consider the sign matrix A from Example 66. By taking A weighted with the following probability distribution P we can get a nearly optimal bound.
P=4Jn−1 0 22n 0 0
With w = P ◦ A as a witness we get a bound of ∥A∥αtr ≥ 23(n−1)/2, which is close to optimal.
The heuristic of taking a witness of the form p ◦ x for a probability distribution p has a very nice characterization in terms of approximate norms. Using duality we see that it is actually equivalent to the ∞-approximate norm.
Theorem 67 Let Φ be a norm on RN, then for every x ∈ {−1,+1}N
Φ∞(x)= max 1 . p:p≥0 Φ∗(p ◦ x)
∥p∥1 =1
Proof The proof follows similar lines to that of Theorem 64. Intuitively, the above expression for Φ∞ is what we expect as this is what one gets by taking the limit as α → ∞ in the expression for Φα in Theorem 64.
Consider the special case Φ = μ. Recall the definition of discrepancy from Chapter 4. It is not hard to check that a reformulation of this definition is
disc(A) = min μ∗(P ◦ A). P:P≥0
∥P∥1=1
Theorem 67 implies that the inverse of discrepancy is equal to μ∞. Note that the approximate norm μα(A) is a decreasing function of α, achieving
77
its minimal value when α = ∞. Thus, the lower bound on randomized communication complexity in terms of the α-approximate μ norm, given in Chapter 4, is a generalization of the discrepancy lower bound and has also been called the generalized discrepancy method.
Dependence of Φα on α We saw in Example 65 that the α-approximate trace norm ∥ · ∥αtr can remain constant as α varies, since ∥Hn∥αtr = 23n/2 for every α ≥ 1. On the other hand, there are also sign matrices A for which the value of μα(A) decreases very rapidly. In particular μ∞(A) can be exponentially smaller than μα(A) for α = 2. For such matrices A, the discrepancy method fails to give good lower bounds on Rε(A), while the lower bound via the bounded α-approximate norm does much better. In particular, this means that for some functions one cannot show a good lower bound via Equation (7.1) simply by choosing a witness of the form w = p ◦ x for a probability distribution p.
A famous example where μα decreases rapidly is the disjointness function.
Claim 68 Consider the 2n × 2n sign matrix An that corresponds to the dis- jointness function. The disjointness function DISJ : {0, 1}n × {0, 1}n → {T,F}isdefinedbyDISJ(x,y)=T ifx∩y=∅andDISJ(x,y)=F other- wise. Then
√5n μ(An) ≥ 2 2 − 1
μ∞(An) ≤ 16n + 8.
Proof Recall from Corollary 27 that γ2(M) ≤ μ(M) ≤ 8γ2(M) for every real matrix M. We show next that γ2∞(An) ≤ 2n + 1.
Denote by Ln the n × 2n Boolean matrix whose columns are the 2n Boolean strings of length n. Then the matrix 2LnLtn − J has the same sign pattern as An and its entries are all larger than 1. Therefore
γ2∞(An) ≤ γ2(2LnLtn − J) ≤ 2n + 1. Now we show a lower bound on γ2(An). Recall that
∥M ∥tr γ2(M) ≥ size(M)
for any sign matrix M. We actually lower bound the trace norm of An. It will be more convenient to work with the Boolean valued matrix Bn = (J−An)/2.
78
This is the Boolean communication matrix for the disjointness function. The matrix Bn is nice to work with because of its tensor product structure; indeed, if we let
1 1 B1= 1 0
then Bn = (B1)⊗n.
As ∥M ⊗ M∥tr = ∥M∥2tr, and a simple calculation shows ∥B1∥tr =
√
5,
we find
which gives the theorem.
∥Bn∥tr = 5n/2,
7.2 Block composed functions
Many functions of interest in communication complexity can be viewed as the composition of an inner function and an outer function. More precisely, the input x to Alice can be broken up into blocks x = (x1,…,xn) and similarly with the input to Bob y = (y1, . . . , yn), so that the communication function h can be expressed as
h(x, y) = (f • gn)(x, y) = f(g(x1, y1), . . . , g(xn, yn)).
Here f and g can be arbitrary Boolean functions of the appropriate size. We call a function h of this form a block composed function, and refer to f as the outer function and g as the inner function.
A well studied class of functions arises when we take the inner function g to be the AND function on one bit. Then if f is the PARITY function, for example, we arrive at the INNER PRODUCT function, and if f is OR we get the SET INTERSECTION function.
Before we discuss lower bounds for block composed functions, let us first think about what we should expect their complexity to be. A fundamental idea going back to Buhrman, Cleve, and Wigderson [BCW98], is that the complexity of f • gn can be related to the query complexity of f and the communication complexity of g. Let RQ(f) indicate the randomized query complexity of f with error probability at most 1/3. This is the number of queries of the form xi =? needed by a randomized algorithm to evaluate f (x) with probability at least 2/3 on the worst case input. Similarly let QQ(f) be the number of queries needed by a quantum query algorithm to evaluate f(x)
79
with success probability at least 2/3. For formal definitions and a survey of query complexity we recommend Buhrman and de Wolf [BW02].
Theorem 69 (Buhrman, Cleve, and Wigderson [BCW98]) For any two functions f : {−1, +1}n → {−1, +1} and g : X × Y → {−1, +1},
R(f • gn) = O(RQ(f)R(g) log RQ(f)) Q(f • gn) = O(QQ(f)Q(g) log n).
Proof We just treat the randomized case here. Let P be a randomized query algorithm for f with success probability 2/3 and making RQ(f) many queries. When P queries the ith bit we run a randomized communication protocol computing g(xi, yi). By repeating this protocol O(log RQ(f)) many times, we can reduce the error probability to be at most (10RQ(f))−1. Then by a union bound, with probability at least 9/10 all such queries will be made correctly, and the decision tree algorithm will answer correctly with proba- bility at least 3/5. By repeating a constant number of times, we can boost this up to 2/3.
Unlike randomized communication complexity, for randomized and quan- tum query complexity we know a polynomially tight characterization in terms of a natural mathematical quantity, the approximate polynomial de- gree.
Definition 70 (approximate degree) Let f : {−1, +1}n → {−1, +1}. The (polynomial) degree of f is the degree of the unique multilinear poly- nomial representing f. For α ≥ 1 we say that a function f′ gives an α- approximate to f if 1 ≤ f′(x)f(x) ≤ α for all x ∈ {−1,+1}n. The α- approximate degree of f, denoted degα(f), is the smallest degree of a func- tion f′ which gives an α-approximate to f.
Remark 71 In a different scenario, one can consider a Boolean valued func- tion f and define the approximate degree as min{deg(f′) : ∥f − f′∥∞ ≤ ε}. Letting f± be the sign representation of f , one can see that this definition with error parameter 0 ≤ ε < 1/2 is equivalent to deg (f ) where α = 1+2ε .
αε ± ε 1−2ε
A polynomial relationship between query complexity and approximate degree was first shown by Nisan and Szegedy [NS94] and later improved by Buhrman et al. [BBC+01].
Theorem 72 ([NS94, BBC+01]) Let f : {−1, +1}n → {−1, +1}. Then RQ(f) ≤ deg2(f)6.
80
This bound holds even with RQ(f) replaced by the deterministic query com- plexity of f. Using this result together with Theorem 69 gives the following corollary:
Corollary 73 For any two functions f : {−1, +1}n → {−1, +1} and g : X×Y →{−1,+1},
R(f • gn) = O(deg2(f)6R(g) log deg2(f)), Q(f • gn) = O(deg2(f)6Q(g) log n).
Our goal, then, in showing lower bounds on the complexity of a block composed function f • gn is to get something at least in the ballpark of this upper bound. Of course, this is not always possible—the protocol given by Theorem 69 is not always optimal. For example, when f is the PARITY function on n bits, and g is the two bit XOR function, this protocol just gives an upper bound of n bits, when the true complexity is constant.
For a broad class of functions, however, we do expect that a lower bound resembling the upper bound of Corollary 73 should hold. In a seminal paper, Razborov [Raz03] showed a theorem of this type. He showed that whenever f is a symmetric function, and g is the AND function the complexity of f • gn is Ω(deg2(f)) by using the approximate trace norm method. This lower bound is polynomially related to the upper bound in Corollary 73.
More recently, very nice frameworks have been developed by Sherstov [She09, She08c] and in independent work by Shi and Zhu [SZ09b] which can show a lower bound on a block composed function f • gn in terms of the approximate degree of f for an arbitrary function f, provided that g satis- fies certain technical conditions. Both of these papers work again with the approximate trace norm, more precisely with the dual formulation of the approximate trace norm as in Equation (7.1). Using this dual form, the problem of showing lower bounds on communication complexity reduces to finding a good witness. A key idea of Sherstov and Shi–Zhu is to define a wit- ness for the approximate trace norm bound in terms of the dual polynomial, described next.
A degree d polynomial which approximates a function f provides a cer- tificate that the approximate degree is at most some value. Similarly, a dual polynomial for f provides a certificate that the approximate polynomial de- gree of f is at least a certain value. More precisely, the dual polynomial has the following properties.
81
Lemma 74 (Sherstov [She08c], Shi-Zhu [SZ09b]) 1 Let f : {−1, +1}n → {−1,+1} and let d = degα(f) for α ≥ 1. Then there exists a function
v : {−1, +1}n → R such that
1. ⟨v,f⟩≥α−1. α+1
2. ∥v∥1 = 1.
3. ⟨v,g⟩ = 0 for any function g of degree ≤ d.
Furthermore, when α = ∞, there is a function v : {−1, +1}n → R satisfying
items (2), (3), and such that v(x)f(x) ≥ 0 for all x ∈ {−1, +1}n.
A function v as above is called a dual polynomial for f. The properties of the dual polynomial mesh very well with the properties required by a good witness in the dual formulation of approximate trace norm. Namely, if v is a dual polynomial for f, to show that the approximate trace norm of f •gn is large we choose as a witness the function v • gn, up to a normalization factor. Item (1) is then used to show that ⟨f • gn, v • gn⟩ is large; item (2) is used to bound ∥v • gn∥1; and, in the most difficult step, item (3) is used to upper bound ∥v • gn∥.
The function g serves as a mediator in the transference of properties of the dual polynomial to the trace norm witness. All that is required of g for the transference of properties (1),(2) is that it is balanced—it outputs the value +1 as often as −1. When g is balanced, the inner product ⟨v,f⟩ and the l1 norm ∥v∥1 are proportional to ⟨v•gn, f •gn⟩ and ∥v•gn∥1, respectively.
Item (3), however, is more difficult, and this is where the papers of Sher- stov [She08c] and Shi and Zhu [SZ09b] diverge. Sherstov considers the case where g is a fixed function of a particularly nice form, which leads f • gn to be what he calls a pattern matrix. The structure of a pattern matrix allows one to compute the spectral norm of v • gn precisely. The pattern matrix framework has proven extremely useful and has found many further appli- cations in unbounded-error communication complexity [She08d, RS08] and multiparty communication complexity [Cha07, LS09a, CA08, BHN08] which will be described in Chapter 8.
Shi and Zhu take a different approach, and are able to get a bound on f • gn in terms of the approximate degree of f whenever g is sufficiently “hard.” This approach simply uses the triangle inequality to upper bound the spectral norm of v • gn. We refer the reader to the survey of Sherstov [She08a] for a detailed comparison of these two methods.
1This is Lemma 3.3.1 of [She08c] and can be found in Section 3.1 of [SZ09b]. 82
We present both the approaches of Sherstov and Shi-Zhu in the next two sections.
7.2.1 Strongly balanced inner function
We begin by describing the pattern matrix method of Sherstov. A pattern matrix can be seen as a block composed function where the inner function g is of the form g : {−1, +1}k × ([k] × {−1, +1}). On input (x, (i, b)) define g(x, (i, b)) = xi · b. In other words, the inner function simply selects a bit of x or its negation. If we let A be a 2k-by-k matrix where A[x,i] = xi we can see that Ag is of the form
Ag=A −A. (7.4)
For a function f : {−1,+1}n → {−1,+1}, the pattern matrix cor- responding to f is a block composed function f(g(x1,y1),...,g(xn,yn)). Notice that the role of g here is to select a bit from each block of x = (x1, . . . , xn), possibly negating some bits, and then applying f to the result- ing n-bit substring. Sherstov shows the following theorem.
Theorem 75 (Sherstov, Theorem 5.1 [She08c]) Let f be an arbitrary function, and let g : {−1, +1}k × ([k] × {−1, +1}) be as described above.
Then
Q∗1/4(f • gn) ≥ 1 deg3(f) log(k) − 2. 2
A key property of pattern matrices which allows for a precise calculation of the spectral norm of v • gn is that the inner function is strongly balanced, as defined next.
Definition 76 (Strongly balanced) Let A be a matrix, and J be the all- ones matrix of the same dimensions as A. We say that A is balanced if Tr(AJt) = 0. We say that A is strongly balanced if AJt = JtA = 0. That is, a matrix is strongly balanced if the sum over each row is zero, and similarly for each column. We say that a function is balanced or strongly balanced if its sign matrix representation is.
Notice in Equation (7.4) that columns of A correspond to the characters of degree one, and hence are balanced. The purpose of b in the construction of a pattern matrix is to also make the rows of Ag also balanced, and thus Ag strongly balanced overall.
83
Lee, Shraibman, and Zhang [LSZ09] observe that Sherstov’s proof of Theorem 75 works essentially unchanged whenever the inner function g is strongly balanced.
Theorem 77 (Lee-Shraibman-Zhang [LSZ09]) Let f : {−1, +1}n → {−1, +1} be an arbitrary function, and let g be a strongly balanced function. Fix 0<ε<1/2, let α=1/(1−2ε), and α0 >α. Then
size(Ag) α0−α Q∗ε(f•gn)≥degα0(f)log ∥Ag∥ +log α(α0+1) .
Proof Letd=degα0(f)andletvbeadualpolynomialforfwithproperties as in Lemma 74. By Theorem 60 and the definition of γ2 given in 2.3.2, the approximate trace norm of Af•gn gives a lower bound on Q∗ε(f • gn). We therefore use the dual expression of the approximate trace norm of Af•gn to prove a lower bound. For this purpose we define a witness matrix B by
2n 11 nn B[x,y]= size(Ag)nv(g(x ,y ),…,g(x ,y )).
Let us first lower bound the inner product ⟨Af•gn,B⟩. Notice that as g is strongly balanced, it is in particular balanced, and so
⟨Af•gn , B⟩ = 2n size(Ag )n
(f • gn)(x, y) · (v • gn)(x, y) x,y
= 2n
f(z)v(z) · |{x, y : gn(x, y) = z}|
size(Ag )n = ⟨f, v⟩
≥ α0 −1. α0 + 1
z∈{−1,+1}n
The third equality is because |{x, y : gn(x, y) = z}| = size(Ag)/2 for balanced functions g, and the last inequality is by Lemma 74. A similar argument shows that ∥B∥1 = 1 as ∥v∥1 = 1.
Now we turn to evaluate ∥B∥. To do this, we expand B in terms of the Fourier coefficients of v. We write
B[x,y] = =
2n size(Ag )n
2 n size(Ag )n
vˆT χT(g(x1,y1),…,g(xn,yn)) T ⊆[n]
vˆ T g ( x i , y i ) T [ i ] T ⊆[n] i∈[n]
84
where T[i] = 1 if i ∈ T and T[i] = 0 otherwise. We can write this more compactly in matrix notation using tensor product
B= 2n vˆTAχ•gn
size(Ag )n
= 2n vˆAT[i]
T ⊆[n]
size(Ag)n T g
T
T⊆[n] i
where A1g = Ag and A0g = J the all-ones matrix of appropriate size.
Now observe that the product AχT •gn AχS •gn is equal to zero whenever
S ̸= T. Indeed,
t A nAt n = AT[i] AS[i]
χT •g
χS •g
g g ii
= AT [i](AS[i])t gg
i
= 0.
When T ̸= S, there is some i for which T[i] ̸= S[i]. The corresponding term is thus either AgJt or JAtg. Either way the product nullifies as g is strongly balanced.
We can therefore use the following fact to analyze ∥B∥. Fact78(Lemma4.2[She08c]) If ABt = AtB = 0 then ∥A+B∥ =
max{∥A∥, ∥B∥}.
This is the key fact which makes Sherstov’s analysis of the spectral norm of pattern matrices so clean. As we shall see in the next section, Shi-Zhu do not assume that the inner function is strongly balanced, and thus simply use ∥A + B∥ ≤ ∥A∥ + ∥B∥ the triangle inequality at this stage.
85
We get
2n
vˆTAχT•gn∥ = n max|vˆT|∥AχT•gn∥
∥B∥= size(Ag)n∥ 2n
T ⊆[n] size(Ag ) T
∥AT [i]∥ =max 2n|vˆT| g
≤
∥Ag∥ size(Ag )
d 1 n/2 size(Ag )
T i size(Ag) ∥AT [i]∥
≤max g
T :vˆT ̸=0 i size(Ag )
In the second to last step we have used that |vˆT | ≤ 1/2n as ∥v∥1 = 1, and in the last step we have used the fact that ∥J∥ = size(Ag).
We conclude that
∥Af•gn∥αtr α0 −α size(Ag)d size(Af•gn) ≥ (α0 +1) ∥Ag∥
.
While it may look strange at first, the expression for the complexity of g in Theorem 77 is closely related to the discrepancy of g with respect to the uniform distribution. Let A be a m-by-n sign matrix. The discrepancy of A with respect to the uniform distribution, discU (A), can be written as
discU(A) = 1 max |xtAy|. size(A) x∈{0,1}m
y∈{0,1}n It is easy to see from this expression that
∥A∥ discU (A) ≤ size(A) .
Shaltiel [Sha03] has shown the deeper result that this bound is in fact poly- nomially tight:
Theorem 79 (Shaltiel) Let A be a sign matrix.
discU (A) = Ω
∥A∥ 3 size(A) .
86
Using this characterization, we get the following corollary:
Corollary 80 In the settings of Theorem 77.
∗ n 1 1 α0−α
Qε(f•g)=degα0(f) 3log discU(Ag) −O(1) +log α(α0+1) . 7.2.2 Triangle Inequality
The method of Shi-Zhu does not restrict the form of the inner function g, but rather works for any g which is sufficiently “hard.” The hardness condition they require is phrased in terms of a somewhat awkward measure they term spectral discrepancy.
Definition 81 (spectral discrepancy) Let A be a m-by-n sign matrix. The spectral discrepancy of A, denoted ρ(A), is the smallest r such that there is a submatrix A′ of A and a probability distribution μ on the entries of A′ satisfying:
1. A′ is balanced with respect to μ, i.e. the distribution which gives equal weight to −1 entries and +1 entries of A′.
2. The spectral norm of A′ ◦ μ is small: ′r
∥A ◦ μ∥ ≤ size(A′)
3. The entrywise absolute value of the matrix A′ ◦ μ should also have a
bound on its spectral norm in terms of r:
′ 1+r
∥|A ◦ μ|∥ ≤ size(A′)
While conditions (1),(2) in the definition of spectral discrepancy are quite natural, condition (3) can be complicated to verify. Note that condition (3) will always be satisfied when μ is taken to be the uniform distribution. Using this notion of spectral discrepancy, Shi-Zhu show the following theorem.
Theorem 82 (Shi-Zhu [SZ09b]) Let f : {−1, +1}n → {−1, +1}, and g : {−1,+1}m1 ×{−1,+1}m2 →{−1,+1}.Ifρ(g)≤deg3(f) then
Here e = 2.718 . . . is Euler’s number. 87
2en Q1/4(f • gn) ≥ Ω(deg3(f)).
Chattopadhyay [Cha08] extended the technique of Shi-Zhu to the case of multiparty communication complexity, answering an open question of Sher- stov [She08a]. In doing so, he gave a more natural condition on the hard- ness of g in terms of an upper bound on discrepancy we shall encounter in Chapter 8, Theorem 93. Following this proof, Lee-Shraibman-Zhang fur- ther relaxed the requirement on the inner function g to simply having small discrepancy under a balancing distribution.
Theorem 83 (Lee-Shraibman-Zhang [LSZ09]) Let f : {−1, +1}n → {−1,+1}, and g : {−1,+1}m1 ×{−1,+1}m2 → {−1,+1}. Fix 0 < ε < 1/2, let α = 1/(1−2ε), and α0 > α. Then
∗ n α0−α Qε(f•g )≥degα0(f)+log α(α0+1) .
Proof
γ2α(Af•gn). By the dual expression for γ2α (Theorem 64) we have γα(A n)=max(1+α)⟨Af•gn,B⟩+(1−α)∥B∥1.
2 f • g B 2 γ 2∗ ( B )
To prove a lower bound we choose a witness matrix B as follows
n B[x,y]=2n ·v(g(x1,y1),…,g(xn,yn))·μ(xi,yi).
i=1
where v witnesses that f has approximate degree at least d = degα0(f).
This definition is the same as in the previous section where μ was simply
the uniform distribution. As argued before, we have ⟨Af•gn,B⟩ ≥ α0−1 and
∥B∥1 = 1 because Ag ◦ μ is balanced. We again expand B as
n
B=2n vˆT(Ag◦μ)T(i),
T :|T |≥d i=1
where(Ag ◦μ)1 =Ag ◦μand(Ag ◦μ)0 =μ.
Now comes the difference with the previous proof. As we do not have
special knowledge of the function g, we simply bound γ2∗(B) using the triangle 88
provided there is a distribution μ which is balanced with respect to g and for which γ∗(g◦μ)≤ degα0(f).
2 2en
As before we use Theorem 60, and thus we really lower bound
α0 +1
inequality.
provided that γ∗(g ◦ μ) ≤
n γ2∗(B)≤2n |vˆT|γ2∗ (Ag◦μ)T(i)
T :|T |≥d i=1
=2n |vˆT|γ2∗(Ag◦μ)|T|γ2∗(μ)n−|T|
T :|T |≥d
≤ γ2∗(Ag◦μ)|T|,
T :|T |≥d
where in the last step we have used that γ2∗(μ) ≤ 1 as μ is a probability distribution and that |vˆT| ≤ 2−n. In the second step (equality) we used the fact that γ2∗ is multiplicative with respect to tensor product, a property proved in [LSŠ08]. We continue with simple arithmetic:
∗ nn∗ i
γ2(B)≤
≤n enγ2∗(Ag◦μ)i
d . 2 2en
i=d
i γ2(Ag◦μ) d
i=d ≤ 2−d
An interesting open question, raised by Sherstov [She08a], is if there are cases where Theorem 83 can be applied where Theorem 77 cannot. While the condition that the inner function g be strongly balanced may seem rather restrictive, as communication complexity is nonincreasing under function re- striction, this theorem can also be applied with respect to a strongly balanced submatrix of g. In this light, the question informally becomes: does every function g for which there is a distribution μ such that g ◦ μ is balanced and γ2∗(g ◦ μ) is small contain a large strongly balanced submatrix?
7.2.3 Examples
In this section we give some examples of the application of Theorem 77. Disjointness Disjointness can be written in the following way.
n
DISJ(x, y) = (xi ∧ yi).
i=1 89
In other words, in this case f is the n-bit OR function, and g is the AND function on one bit. Notice that the sign matrix of the AND function on one
bit looks as follows.
1 1 H= 1 −1
This matrix is not strongly balanced. Sherstov gets around this problem in the following way. We can alternatively think of the disjointness function on n bits (assuming that four divides n) as
n/4 DISJ(x,y)=∨3j=0(x4i+j ∧y4i+j)
i=1
Here we take f to be the OR function on n/4 bits and g to be the OR-AND function on 4 bits.
Now g does contain a strongly balanced submatrix. Namely,
0001 0010 1000 0100 0011 −1 −1 1 1 0101 −1 1 1 −1 1100 1 1 −1 −1 1010 1 −1 −1 1
√
One can check that the spectral norm of this matrix is 2 2. Indeed, we can write the spectral norm of this matrix as
− H H − H 0 0 H √ H −H ≤ 0 −H + H 0 =2 2.
This gives us
size(Ag′ ) = √2 ∥Ag′∥
function on n bits is Ω( n), and so we get a Ω( n) lower bound for the disjointness function.
When g is inner product When g is the inner product function on k- bits, the sign matrix Ag is a 2k-by-2k Hadamard (Sylvester) matrix Hk. This matrix can be defined recursively by H0 = [1] and
Hk−1 Hk−1 Hk = Hk−1 −Hk−1
90
Nisan and Szegedy [NS94] show that the bounded-error degree of the OR
√√
From this definition we can see that Hk contains a strongly balanced submatrix of size 2k−1-by-2k−1 for all k > 1. For k > 1 we can write Hk as
has spectral norm 2
2k−1 and so we obtain 2
Hk−2 Hk = Hk−2 H k − 2 Hk−2
Hk−2 −Hk−2 H k − 2 −Hk−2
Hk−2
Hk−2 − H k − 2 −Hk−2
Hk−2 −Hk−2
Hk−2 −Hk−2 − H k − 2
Hk−2
The submatrix sitting in the middle
−Hk−2 Hk−2
is clearly strongly balanced and is of dimension 2k−1-by-2k−1. This matrix
√
Q∗1/4(f • gn) ≥ (k − 1) deg3(f) − O(1)
for any function f, when g is the inner product function on k bits. 7.2.4 XOR functions
As we have hopefully demonstrated, the dual polynomial of f can be a very powerful technique for choosing a witness when working with a block composed function. In this section, however, we will consider a case when the lower bound in terms of approximate degree, Theorem 77, does not show a good lower bound.
Say that the inner function g = ⊕(x, y) is the XOR function on one bit. This is a strongly balanced function, so we can apply Theorem 77. In this case, however, the theorem gives nothing as Ag is a rank-one matrix and ∥Ag∥ = size(Ag). Indeed, we should expect this as when f is the PARITY function, the complexity of f • gn is constant.
When g is the XOR function, it turns out that the complexity of f • gn is not related to the approximate degree of f, but to the approximate l1 norm of the Fourier coefficients of f. Let us define this next.
Definition 84 Let f : {−1, +1}n → {−1, +1} be a Boolean function. De- ˆ
note by ∥f∥1 the l1 norm of the Fourier coefficients of f. In the usual way we also define the approximate version of this norm: for α ≥ 1, let
ˆα
∥f∥1 = min ∥gˆ∥1
g:1≤g(x)f (x)≤α
91
Theorem 85 Let f : {−1, +1}n → {−1, +1} be an arbitrary function, and g(x, y) = ⊕(x, y) be the XOR function on one bit. Let A be the sign matrix representation of f • gn. Then
∥A∥αtr ˆ α size(A) = ∥f ∥1 .
Proof We show the lower bound first. For this, we will use the general formulation of the dual of an approximate norm from Theorem 64. The dual
ˆ
norm of ∥f∥1 is given by ˆ∗
∥f∥1 = max ⟨f,u⟩ u:∥uˆ∥1 =1
= max fˆ⟨χ ,u⟩=2nmax|fˆ|. TTT
u:∥uˆ∥1 =1 T T ˆ∗nˆ
Thus we see that ∥f∥1 = 2 ∥f∥∞.
By the general formulation of the dual of an approximate norm, this
means that there is a function v such that
(1+α)⟨v,f ⟩+(1−α)∥v∥1
1. 2 = ∥f ∥1 .
2. 2n∥vˆ∥∞ ≤ 1,
We now define a witness to show that the approximate trace norm of A
ˆα
is large as
2n 11 nn B[x,y]= size(Ag)nv(g(x ,y ),…,g(x ,y )).
As argued in the proof of Theorem 77, item (1) can be used to show that
(1+α)⟨A,B⟩+(1−α)∥B∥1 ˆ α 2 = ∥f ∥1 .
Now we use item (2) to show ∥B∥ ≤ 1. We will again use the fact that g is strongly balanced and so the matrices AχT •gn corresponding to distinct T are orthogonal.
2n size(Ag )
∥B∥ = size(Ag)n ∥
=
= max |vˆT |.
T ⊆[n]
T ⊆n i
2n T[i]
∥ nmax|vˆT| ∥Ag ∥
vˆT Ag T[i]
T⊆n
92
The last step follows since when g is the XOR function on one bit we have ∥Ag∥ = ∥J∥ = size(Ag) = size(Ag)/2. This gives the desired lower bound as by property (2)
11 max|vˆT|≤ n= .
T⊆n 2 size(A)
Now we turn to the upper bound. Let w be a function such that 1 ≤
ˆα w(x)f(x) ≤ α and ∥wˆ∥1 = ∥f∥1 . Define
B[x, y] = w(g(x1, y1), . . . , g(xn, yn)).
Then clearly 1 ≤ A[x, y]B[x, y] ≤ α. To bound the trace norm of B we will usethefactthatifXYt =XtY =0then∥X+Y∥tr =∥X∥tr+∥Y∥tr. This gives
∥ B ∥ = ∥ wˆ A T [ i ] ∥ tr T g
T ⊆[n]
=wˆ ∥AT[i]∥
Tg T⊆n i
ˆα = size(A)∥f ∥1 .
Remark 86 This theorem can be alternatively proven as follows. Let f : {−1,+1}n →{−1,+1}andAbethesignmatrixwhereA[x,y]=f(x⊕y). It is easy to see that
∥A∥tr
size(A) = l1(f)
as the (unnormalized) eigenvectors of A are given by the characters χS (x) = i∈Sxi forS⊆{0,1}n.
By a symmetrization argument one can then show that, without loss of generality, the matrix B of minimal trace norm which gives an α-approximation to A is of the form B[x,y] = g(x⊕y) for a function g which gives an α- approximation to f.
Shi and Zhang [SZ09a] are able to completely determine the randomized and quantum complexities of XOR functions in the case of symmetric f. For the lower bound they do not use the above approach, but rather a reduction to the case of f (x ∧ y). We record their result here.
93
ˆ
Theorem 87 (Shi and Zhang [SZ09a]) Let S : [n] → {−1, +1} and de- fine a sign matrix A[x, y] = S(|x ⊕ y|). Let r0, r1 ≤ n/2 be the minimum integers such that S(k) = S(k + 2) for all k ∈ [r0, n − r1). Then
R1/4(A) = O(r1 + r2) Q1/4(A) = Ω(r1 + r2).
94
Chapter 8
Multiparty communication complexity
In this chapter we look at communication complexity where the input is dis- tributed over k-many players who wish to evaluate a function f(x1, . . . , xk). There are two common ways of distributing the inputs among the play- ers, leading to the number-in-hand and number-on-the-forehead models. In the case of two players, both of these models specialize to the usual model of two-party complexity. In the number-in-hand model, player i receives input xi. In the number-on-the-forehead model, player i receives (x1, . . . , xi−1, xi+1, . . . , xk), i.e. the entire input except for xi. Here one can picture the input xi sitting on the forehead of player i.
Deterministic and randomized communication complexity in the multi- party model are defined similarly as in the two player model. We will only deal with the public coin model of multiparty complexity, thus a randomized multiparty protocol is simply a probability distribution over deterministic protocols. It is common in multiparty communication complexity to take a generous model of communication and assume that the players write their messages on a blackboard that is seen by everyone. We denote k-party de- terministic communication complexity by Dk. Randomized communication complexity with error bound ε is denoted by Rεk. The superscripts are omit- ted when k is clear from the context. If the subscript is omitted it is assumed that ε = 1/3.
The study of both the number-in-hand and number-on-the-forehead mod- els have interesting applications. As shown by a seminal paper of Alon, Matias, and Szegedy [AMS99], lower bounds on disjointness in the number- in-hand model have applications to showing lower bounds on the memory
95
requirements of streaming algorithms. In the number-on-the-forehead model as well, Beame, Pitassi, and Segerlind [BPS06] have shown that lower bounds on disjointness have interesting applications to lower bounds on proof com- plexity. Finally, and perhaps the greatest motivation to the study of the number-on-the-forehead model, is that lower bounds here imply circuit com- plexity lower bounds. In particular, showing an explicit function which requires super-polylogarithmic complexity in the number-on-the-forehead model with super-polylogarithmic many players would give an explicit func- tion outside of the circuit complexity class ACC0, currently a major open problem. Currently the best lower bounds in the number-on-the-forehead for explicit functions are of the form n/2k for k-players. The applications of multiparty complexity are discussed in more detail in Chapter 9.
To give a flavor of the difference between the number-in-hand and number- on-the-forehead models, let us consider the equality problem EQn. This is defined as EQn(x1,…,xk) = T if all of the n-bit strings x1,…,xk are all equal, and F otherwise. In the number-in-hand model of communication complexity a lower bound of n can be proved for EQn by a reduction to the 2-player case. On the other hand there is a 2-bit protocol for the equality problem in the number-on-the-forehead model for k ≥ 3 players. In this protocol player 1 and player 2 check if all the inputs they observe are equal, and output T if they are and F otherwise. It is not hard to check that this protocol is correct.
8.1 Protocol decomposition
Let X be a finite set and consider a multiparty function f : Xk → {−1, +1}. We will associate this function with a k-dimensional tensor Af, known as the communication tensor, where Af[x1,…,xk] = f(x1,…,xk).
As in the case of two-party deterministic communication complexity, we first look at the decomposition of the communication tensor into simpler objects which is induced by a correct communication protocol. Recall that in the case of two-party deterministic complexity, these simpler objects were monochromatic combinatorial rectangles.
In the number-in-hand model, the analog of combinatorial rectangles are the natural higher dimension version of these objects. In other words, we now consider combinatorial cubes of the form I1 × I2 × · · · × Ik , where each Ij ⊆X.
In the number-on-the-forehead model, the analog of combinatorial rect- angles are more complicated objects known as cylinder intersections. A
96
cylinder in the ith dimension is a set Ci ⊆ Xk which does not depend on the ith coordinate. In other words, if (x1,…,xi−1,xi,xi+1,…,xk) ∈ Ci then also (x1,…,xi−1,x′i,xi+1,…,xk) ∈ Ci for every x′i ∈ X. One can see how such sets might be relevant to number-on-the-forehead complexity as the message of the ith player does not depend on the ith input. A cylinder intersection C is a set which can be written as the intersection of cylinders: C = C1 ∩ . . . ∩ Ck .
Theorem 88 (NIH partition bound) A successful c-bit deterministic number- in-hand communication protocol for f partitions the communication tensor
into at most 2c combinatorial cubes which are monochromatic with respect to
f.
Theorem 89 (NOF partition bound) A successful c-bit deterministic number- on-the-forehead communication protocol for f partitions the communication matrix into at most 2c cylinder intersections which are monochromatic with respect to f.
As in the two-party case, we can use the partition bound to define an appropriate norm to bound multiparty communication complexity. From now on, we focus on the number-on-the-forehead model. Usually, it will be straightforward to transfer the elements of the discussion to the number-in- hand model as well. Also we should point out that for the number-in-hand model information theoretic lower bounds often give better lower bounds [CKS03, BYJKS04] than the norm based approach we outline here. On the other hand, it is not known how to extend these information theoretic techniques to the number-on-the-forehead model.
A characteristic tensor of a set F ⊆ X k is the (0, 1) tensor χF satisfying χF[x1,…,xk] = 1 if and only if (x1,…,xk) ∈ F. By a slight abuse of notation we identify a set with its characteristic tensor.
Definition 90 (Cylinder intersection norm) Let M be a k-tensor. De- fine
μ(M) = min |αi| : M = αiCi
ii where each Ci is a cylinder intersection.
Notice that when M is a matrix, this reduces to the μ norm we have seen before.
97
As in the two-party case, the following theorem is immediate from the partition bound.
Theorem 91 Let A be a sign k-tensor. Then D(A) ≥ log(μ(A)).
Also in direct analogy with the two-party case Theorem 44, we can show that the approximate version of μ can be used to lower bound randomized number-on-the-forehead complexity.
Theorem 92 Let A be a sign k-tensor, and 0 ≤ ε < 1/2. Then Rε(A) ≥ log(μα(A)) − log(αε)
where αε = 1/(1 − 2ε) and α ≥ αε.
Finally, discrepancy of cylinder intersections (sometimes called multi- party discrepancy) is also defined as in the two player case. By Theorem 67 the bound given by the multiparty discrepancy method of a sign tensor A is equal to μ∞(A).
8.2 Bounding number-on-the-forehead discrepancy
Cylinder intersections are difficult combinatorial objects. After much effort, there is still essentially just one technique available for bounding multiparty discrepancy. This technique appeared in the early paper of Babai, Nisan, and Szegedy [BNS89]. Moreover, this technique is inherently limited to showing lower bounds of the form n/2k. Thus one of the major obstacles to show- ing non-trivial bounds on number-on-the-forehead complexity for more than log n players is finding alternative lower bound approaches.
The next statement is from [BNS89], see also [Chu90, Raz00] for similar formulations.
Theorem 93 Let M be a k-tensor. Then
2k μ∗(M)
≤ E 0 1 M[xl1,xl2,...,xlk]
size(M) x ̄,x ̄ 12 k l∈{0,1}k
where x ̄0 = (x01,...,x0k) and similarly x ̄1 = (x1,...,x1k). 98
The following variant of the bound of [BNS89] first appeared in [Cha07] for use with the pattern tensor framework.
Theorem 94 Let M be a k-tensor of dimensions n1,n2,...,nk, and let size(M) = n1n2 ···nk be the number of entries in M. Denote by (M •1 M) the (2k − 2)-tensor defined by
Then
M[x,yl1,...,ylk−1]. 1 k−1
l∈{0,1}k−1
μ∗(M) 2k−1
size(M) ≤ Ey ̄0,y ̄1 |(M •1 M)|,
(M •1 M)[y10,y1,...,yk0−1,yk1−1] = Ex
where y ̄0 = (y10, . . . , yk0−1) and similarly y ̄1 = (y1, . . . , yk1−1).
Both theorems are proved using repeated application of Cauchy-Schwarz inequality—it is applied k times for the first theorem, and k − 1 many times for the second.
8.2.1 Example: Hadamard tensors
We give an example to show how Theorem 94 can be used in conjunction with duality. This example is similar to Example 65. Let H be a N-by-N Hadamard matrix. We show that μ∞(H) ≥ √N. Indeed, simply let the witness matrix be H itself. With this choice
μ∞(H)≥⟨H,H⟩= N2 μ∗(H) μ∗(H)
Now we bound μ∗(H) using Theorem 94 which gives: μ∗(H)2 ≤ N4 E|H •1 H| = N3
as H •1 H has nonzero entries only on the diagonal, and these entries are of magnitude one.
Ford and Gál [FG05] extend the notion of matrix orthogonality to tensors, defining what they call Hadamard tensors.
Definition 95 (Hadamard tensor) Let H be a sign k-tensor. We say that H is a Hadamard tensor if
(H •1 H)[x02,x12,...,x0k,x1k] = 0 whenever x0i ̸= x1i for all i = 2,...,k.
99
The “orthogonality” property of Hadamard tensors combined with The- orem 94 imply
∗ 2k−1 Nk2k−1 μ (H) ≤(k−1) N .
The simple proof above for Hadamard matrices can now be easily extended to Hadamard tensors:
Theorem 96 (Ford and Gál [FG05]) Let H be a Hadamard k-tensor of side length N. Then
∞ N 1/2k−1 μ (H)≥ k−1
Remark 97 By doing a more careful inductive analysis, Ford and Gál obtain this result without the k − 1 term in the denominator. They also construct explicit examples of Hadamard tensors.
8.3 Pattern Tensors
We now define a natural generalization of the pattern matrices of Sherstov [She09, She08c] to the tensor case. This generalization was first defined, in a slightly different form, by Chattopadhyay [Cha07]. Like a pattern matrix, a pattern tensor can be thought of as a block composed function. The outer function f : {−1,+1}n → {−1,+1} can be arbitrary. Let us now describe the inner function g. The inner function takes k arguments—the first argument can be thought of as a k−1 dimensional tensor, and the other k − 1 arguments as indices into the sides of this tensor. Thus
g(x,y1,...,yk−1) = x[y1,...,yk−1].
Fix an integer N. As a whole, the pattern tensor Af,N is then defined such
that Af,N[x,y1,...,yk−1] is equal to
f(g(x1, y1[1], . . . , yk−1[1]), . . . , g(xn, y1[n], . . . , yk−1[n])).
Here x is a k dimensional sign tensor with dimensions n × N × ··· × N, xi is the k − 1 dimensional tensor achieved by constraining the first index of x to be equal to i. The yj’s are vectors of indices in [N]n, and yj[i] is the ith element of the jth vector.
Notice that here the definition of the inner function g is less sophisticated than that used for pattern matrices. For pattern matrices, remember that a key feature is that they are strongly balanced. In the matrix case, having
100
g be strongly balanced aided substantially in evaluating the spectral norm of a pattern matrix. In the tensor case, however, instead of using spectral norm we are using the more blunt tool of the theorem of [BNS89]. Here it is not clear that being strongly balanced is of any help, so we stick to this simpler definition of g.
Pattern tensors satisfy the following.
Theorem 98 ([LS09a, CA08]) Let f : {−1, +1}n → {−1, +1} be a boolean function, then
logμα(Af,N) ≥ degα0(f) +log α0 −α, 2k−1 α0 + 1
for every 1 ≤ α < α0 < ∞, provided N ≥ 2e(k−1)22k−1n. degα0 (f )
By now the reader should be able to guess the sketch of the proof of Theorem 98. We use the dual formulation of μα and take as a witness the pattern tensor of the dual polynomial. Namely, if v is the dual polynomial as in Lemma 74 we take as our witness the pattern tensor Q = Qv,N . That is, Q[x,y1,...,yk−1] is equal to
v(g(x1, y1[1], . . . , yk−1[1]), . . . , g(xn, y1[n], . . . , yk−1[n])).
Just as we saw in Section 7.2, the dual formulations of approximate degree and approximate norm fit well together. This makes handling the numerator in the max formulation of μα very easy. The inner product ⟨Af,N , Qv,N ⟩ is proportional to ⟨f, v⟩ and similarly ∥Qv,N ∥1 is proportional to ∥v∥1, with the
same ratio size(Q). It is therefore left to bound μ∗(Q) in terms of something 2n
proportional to degα0(f). Here we first prove such a relation for the case k = 2, and then extend it to general k. Such a result in the two-party case, using the Babai, Nisan, Szegedy method 94 to upper bound the discrepancy of a pattern matrix, was first shown by Sherstov [She09].
Lemma 99 ([She09]) Let v : {−1, +1}n → R be a function satisfying: 1. ∥v∥1 ≤ 1,
2. vˆT = 0 for every T ⊆ [n] with cardinality |T| ≤ d.
Take Q = Qv,N be the pattern matrix corresponding to v. Then
provided that N ≥ 2en/d.
μ∗(Q) ≤ size(Q), 2n+d/2
101
Proof Consider the definition of a pattern tensor. In the two dimensional (matrix) case, the input x is an n×N sign matrix, and y is a vector in [N]n. By Theorem 94 we have
μ∗(Q) 2
size(Q) ≤Ey0,y1 ExQ[x,y0]Q[x,y1]. (8.1)
To estimate the inner expectations over x, we use the Fourier representation v=TvˆTχT ofv.
We can express Q as a linear combination Q = T vˆT χT ,N , where χT ,N is the pattern matrix corresponding to the character χT . Now the right hand side of (8.1) becomes
Ey0,y1 Ex vˆTvˆT′χT,N[x,y0]χT′,N[x,y1]. T ,T ′
By linearity of expectation and the triangle inequality this is bounded by
|vˆTvˆT′|Ey0,y1 ExχT,N[x,y0]χT′,N[x,y1]. T,T′
We now use the properties of v. First, ∥v∥ ≤ 1 and therefore |vˆ | ≤ 1 . 1 T2n
In addition vˆT = 0 for every set T with |T | ≤ d. We therefore arrive at the following expression
1
22n
T,T ′:|T |,|T ′|>d
This is equal to
1
22n
T,T ′:|T |,|T ′|>d
Ey0,y1 ExχT,N[x,y0]χT′,N[x,y1].
0 1 Ey0,y1 Ex x[i,y [i]] x[j,y [j]].
i∈T j∈T′
The expectation inside the absolute value is equal to 0 if T ̸= T′, and also if T = T′ but there is an element i ∈ T such that y0[i] ̸= y1[i]. The value of this expectation is 1 in all other cases. Our expression is therefore equal to
1 Pr ∀i∈T ,y0[i]=y1[i]
22n y0,y1 T :|T |>d
102
For a set T of cardinality |T| = t, we have
Pr ∀i∈T ,y0[i]=y1[i]≤N−t.
y0,y1
Therefore, the sum of these probabilities above can be bounded as follows
1 n n −t 1 n ent 22n tN ≤22n dN
t=d+1 t=d+1 ≤1,
22n+d
assuming N ≥ 2en/d. Plugging this back into (8.1) we get the desired result.
The extension of Lemma 99 to general k is:
Lemma 100 ([Cha07, LS09a, CA08]) Let v : {−1, +1}n → R be a func-
tion satisfying:
1. ∥v∥1 ≤ 1,
2. vˆT = 0 for every T ⊂ [n] with cardinality |T| ≤ d.
Take Q = Qv,N be the pattern k-tensor corresponding to v. Then μ∗(Q) ≤ size(Q) ,
provided that N ≥ 2e(k−1)22k−1n. d
2n+d/2k−1
Proof
applied
The proof starts as the proof of Lemma 99. First, Theorem 94 is
μ∗(Q) ≤ E 0 1 E size(Q) y ̄,y ̄x
2k−1
the Fourier representation of v. Denote by [n] the family of subsets of [n] >d
[n]2k−1 k−1 whose size is larger than d, and let T = >d be the family of 2
-tuples
of subsets from [n]. Then, >d
1 22k−1n
(T1 ,…,T2k−1 )∈T
E0 1 E y ̄ ,y ̄ x
l∈{0,1}k−1 103
l[1] l[k−1] χ [x,y ,…,y ].
Q[x,yl[1],…,yl[k−1]], 1 k−1
l∈{0,1}k−1
where y ̄0 = (y10,…,yk0−1) and similarly y ̄1 = (y1,…,yk1−1). Now we use
Tl,N 1 k−1
By definition of χTl,N this is equivalent to
1 22k−1n
(T1,…,T2k−1)∈T
E 0 1
y ̄ ,y ̄ x
l[1] 1
l[k−1] k−1
[i]] .
μ(Q) ≤ 22k−1n
k−1 n
E
x[i,y
[i],…,y
l∈{0,1}k−1 i∈Tl
As we have seen in Lemma 99, the inner expectation can be equal to
either 0 or 1. The value 1 is obtained if and only if every vector of indices
(i, yl[1][i], . . . , yl[k−1][i]) that appears in the expression inside the expectation, 1 k−1
appears there an even number of times. Thus, to complete the proof, we bound the probability of this event. Clearly, a sufficient condition for this event not to hold is that there is some i ∈ l Tl such that the 2k−1 possible
vectors (yl[1][i], . . . , yl[k−1][i]) for l ∈ {0, 1}k−1, are all distinct. Namely, for 1 k−1
every m = 1…k−1, ym0 [i] ̸= ym1 [i]. If this condition holds we call the index i, nondegenerate, and i is called degenerate otherwise.
Suppose that for some choice of y10, . . . , yk0−1, y1, . . . , yk1−1 there are g many degenerate indices i ∈ [n]. By the above reasoning the number of sets (T1,…,T2k−1)∈T whichleadtoanonzeroexpectationisatmost
g 2k−1
gr ≤2g2k−1. r=d+1
Now we bound the probability that for y10,…,yk0−1,y1,…,yk1−1 there are g many degenerate indices. The probability that ym0 [i] ̸= ym1 [i] is 1/N. Thus by a union bound, the probability that a single index is degenerate is at most (k − 1)/N. Finally, as each index is chosen independently, the probability of g many degenerate cubes is at most
n k − 1 g gN.
Putting everything together we have
k−1 ∗ 2k−1 size(Q)2
n
nk−1 g2k−1
g
g=d+1 ≤ size(Q)2
g=d+1
g N 2 k−1 g
e(k − 1)22 n dN
22k−1 n size(Q)2k−1
≤ 22k−1n+d . 104
The last step holds, provided that N ≥ 2e(k − 1)22k−1 n/d.
8.4 Applications
8.4.1 The complexity of disjointness
As mentioned, the best lower bound proved so far on the NOF communi- cation complexity of a k-tensor is of the form n , where n is the size of
2k−1
the input [FG05] (see also Section 8.2). This bound is proved using discrep-
ancy, and as long as we use Theorem 94 to bound discrepancy, this 2k−1 factor will remain. Improving on this is a big open problem in multiparty communication complexity. In particular, an explicit function which requires super-polylogarithmic complexity in the number-on-the-forehead model with super-polylogarithmic many players would give an explicit function outside of the circuit complexity class ACC0 (see Chapter 9). But even within this limit, lower bounds on the communication complexity of explicit functions in the number-on-the-forehead model have strong applications.
Beame et al [BPS06] showed that an ω(log4 n) lower bound for 3-party communication complexity of the set-disjointness function, implies super- polynomial lower bounds on tree-like Lovász-Schrijver proof systems that refute unsatisfiable CNF’s. More generally, a strong lower bound on (k + 1)- party number-on-the-forehead communication complexity of set-disjointness implies a strong lower bound for all tree-like proof systems whose formulas are degree k polynomial inequalities.
Let ORn : {0, 1}n → {−1, +1} be the OR function on n bits, then the k-part set-disjointness function DISJk,n : ({0,1}n)k → {−1,+1} is defined as DISJk,n(x1, . . . , xk) = ORn(x1 ∧ x2 . . . ∧ xk).
Recall the discussion from Section 8.3, about the dependency of μα on
α. We saw that μα(DISJ2,n) decreases very rapidly as α tends to infin-
ity. In particular in Lemma 68 we proved that μ∞(DISJ2,n) = O(n), while √5n
μ(DISJ2,n) ≥ 2 . Thus the discrepancy bound yields weak results for this function. In Section 7.2.3 we proved that for bounded approximation it
holds that μ2(An) ≥ Ω(2 n), by reduction to approximate degree, and we will see in Chapter 5 that this is tight.
The situation with the k-party set-disjointness function DISJk,n, for k ≥ 3, seems similar. The extension of the upper bound on μ∞(DISJk,n) is quite straightforward. And exponentially better bounds can be proved for
105
√
μ2(DISJk,n):
Theorem 101 ([LS09a, CA08]) For every k and n
n1/(k+1) R(DISJk,n) ≥ Ω 22k .
Observe that the lower bound on DISJk,n becomes weaker as k grows. It is reasonable to assume that even for k = 3 the lower bound is no longer tight. The lower bounds on k-party set-disjointness are proved by a reduction to pattern tensors of Section 8.3.
Proof For integers m,M, let Am,M be the pattern tensor that corre- sponds to ORm. We show that Am,M is a subtensor of DISJk,n. Recall that Am,M[x,y1,…,yk−1] is equal to
OR(x[1, y1[1], . . . , yk−1[1]], . . . , x[m, y1[m], . . . , yk−1[m]]).
Here we consider x as a k-dimensional Boolean tensor with dimensions m×M ×···×M, and the yi’s are vectors of m indices in [M]. Thus the k − 1 inputs y1, . . . , yk−1 serve as pointers into the first input x. Then the OR function is invoked on the m bits of x which are selected by the inputs {yi}. Let us interpret the disjointness function in a similar manner, namely
DISJ[x,z1,…,zk−1]=OR(x∧(z1 ∧···∧zk−1)).
Since the OR function only cares about the 1 inputs in x, we can think of disjointness as the OR function invoked on the bits of x where the vector (z1 ∧ · · · ∧ zk−1) is equal to 1. In other words, first the zi’s select the set of bits where they are all equal to 1, then OR is called upon those bits in x.
Thus, the only obstacle in relating the pattern tensor Am,M with dis- jointness is in the manner in which the last inputs point into the first. This difference can be bridged though. Let x, y1, . . . , yk−1 be inputs to Am,M . We associate each yi with a Boolean tensor zi of dimensions m × M × ··· × M defined as follows: zi is equal to 1 on inputs of the form (t, s1, . . . , si−1, yi[t], si+1, . . . , sk−1), and is equal to zero on all other inputs. With this definition it is not hard to check that the vector (z1 ∧ · · · ∧ zk−1) points into x exactly the same way as y1,…,yk−1. We see therefore that Am,M is a subtensor of DISJk,n where n = mMk−1.
Now, back to the lower bound. By Theorem 98
log μ2(Am,M ) ≥ deg3(ORm) − O(1), 2k−1
106
provided M ≥ 2e(k−1)22k−1 m . Nisan and Szegedy [NS94] show that deg3(ORm) = √ deg3 (ORm )
Ω( m), thus
2 √m logμ (Am,M)≥Ω 2k−1
,
provided M ≥ Ω 22k √m. Theorem 92 implies that this lower bound
holds for the randomized communication complexity of Am,M as well. Since Am,M is a subtensor of DISJk,n for n = mMk−1, or alternatively for √m =
k+1
Θ(n 1 /22k ), we get
n1/(k+1) R(DISJk,n) ≥ Ω 22k .
on-the-forehead randomized communication complexity of set-disjointness, which is nontrivial up to Θ(log1/3 n) players. Beame and Huynh-Ngoc show their results by reducing the communication complexity problem to a stronger notion of approximate degree which they call (ε,α)-approximate degree. This notion of degree is not easy to handle, but they give a general technique to convert functions of large approximate degree to functions of large (ε, α)- approximate degree. This technique cannot be applied directly to OR, thus their lower bounds on set-disjointness is proved via reduction. In addition to the new notion of approximate degree, they also use pattern tensors with other classes of inner functions g, than the one presented in Section 8.3.
8.4.2 Separating communication complexity classes
It is interesting to compare the strength of different types of communication protocols, deterministic vs. nondeterministic, deterministic vs. randomized etc. The example of the identity function from Chapter 4 demonstrates that randomized protocols can be much more powerful than deterministic ones. As we saw, for this simple function there is a randomized protocol which requires constant number of bits, while there is no deterministic pro- tocol that is more efficient than the trivial one. Randomized protocols are known to be more powerful than deterministic ones also for k-party number- on-the-forehead multiparty communication complexity with k up to nO(1)
107
Observe that Theorem 101 provides a nontrivial lower bound on DISJk,n only as long as the number of players is at most log log n. Beame and Huynh-
√√
Ngoc obtained a lower bound of the form Ω(2 log n/ k−k) on k-party number-
[BDPW07]. When k ≥ 3, though, this separation is not proved for an ex- plicit function, but rather via a counting argument. Note that an explicit separation for k ≥ 3 seems to require new ideas, as there is currently no lower bound technique for deterministic number-on-the-forehead communi- cation complexity that does not also hold for randomized communication.
The set-disjointness function of Section 8.4.1 demonstrates that nonde- terministic protocols can be much stronger than randomized protocols, and thus also deterministic ones. There is a simple nondeterministic protocol for the set-disjointness, as we have seen in Chapter 3 for two players. It is more convenient to specify this protocol for the complement function set- intersection: The players nondeterministically guess a coordinate, then the players output 1 if their input is equal to 1 on that coordinate. The output of the protocol is 1 if all players wrote 1 on the blackboard, and the output is 0 otherwise. Certainly, if the player’s subsets intersect there is a guess which leads to an output of 1. While if the sets do not intersect then all guesses leads to an output of 0. Thus the nondeterministic communication complex- ity of Dk,n is O(logn). On the other hand, by results from Section 8.4.1 for 2-players, and Section 8.4.1 for up to log log n players, the randomized communication complexity of set-intersection is exponentially larger. Using similar techniques as in Section 8.3 David, Pitassi, and Viola [DPV08] give an explicit function which separates nondeterministic and randomized number- on-the-forehead communication complexity for up to Ω(log n) players. They are also able, for any constant c to give a function computable in AC0 which separates them for up to c log log n players. (Note that disjointness can be also computed in AC0.)
In fact the above simple nondeterministic protocol for set-intersection provides another explanation for why the discrepancy method yields bad bounds for set-disjointness, as discrepancy is also a lower bound on nonde- terministic communication complexity:
Theorem 102 For any sign k-tensor A
Nk(A) ≥ log μ∞(A) − O(1).
108
Chapter 9
Upper bounds on multiparty communication complexity
The study of multiparty communication complexity has applications to many other models of communication. Often these results take on the following form: an efficient algorithm for a problem f in some computational model results in an efficient multiparty communication protocol for some related function g. Of course this means that by showing lower bounds on the mul- tiparty communication complexity of g one can obtain lower bounds in the desired computational model. Some examples of results of this type are:
1. Streaming algorithms is a burgeoning field designed to compute prop- erties of massive data sets too large to be stored in memory in their entirety. A seminal paper in this field [AMS99] shows that algorithms to compute some important features of a data stream lead to efficient algorithms for a promise version of DISJOINTNESS in the multiparty number-in-hand model.
2. Beame, Pitassi, and Segerlind [BPS06] show that efficient refutations of certain unsatisfiable formulas in a broad class of proof systems give rise to efficient algorithms for DISJOINTNESS in the multiparty number- on-the-forehead model.
3. Work of [All89, Yao90, BT94, HG91] has given a huge motivation to the study of the number-on-the-forehead model by showing that func- tions with small ACC0 circuits have efficient number-on-the-forehead protocols. ACC0 is the class of languages which can be computed by polynomial size circuits of constant depth using AND, OR, NOT and MOD m gates for any m.
109
Fortunately, the reductions involved for items (1),(3) are relatively easy and we will present them below. The argument for item (2) is fairly involved and we refer the reader to the paper of Beame, Pitassi, and Segerlind for more details.
We will also discuss an upper bound on multiparty communication com- plexity in the more traditional sense. This is a clever protocol of Grol- musz [Gro94] which shows that any problem of the form f (x1 ∧ . . . ∧ xk ) for a symmetric function f has a number-on-the-forehead protocol of com- plexity roughly k2n/2k. Showing a lower bound on an explicit function for more than k = logn players is a major open problem, with serious impli- cations by item (3) above. This protocol illuminates the surprising power of the number-on-the-forehead model and part of the difficulty to break the k = log n barrier.
9.1 Streaming lower bounds
We are increasingly exposed to large amounts of data. Sometimes we would like to compute some features of this data, but storing it in its entirety is infeasible. Imagine instead that the data is streaming by and we only have a small amount of memory to use to take notes as it passes. Can we still compute meaningful properties of the data in this scenario?
Many important properties of the data can be learned from its frequency moments Consider a stream a = a1 . . . am consists of m elements from a universe [n]. For i ∈ [n], let ci be the number of occurrences of i in the string a. Then the kth frequency moment, Fk is
F k = c ki . i
Notice that F0 is simply the number of distinct characters in the string and F1 is the length of the string. We define F∞ to be
F∞ =maxci. i
In a seminal paper, Alon, Matias, and Szegedy [AMS99] consider the com- plexity of streaming algorithms computing frequency moments. Somewhat surprisingly, they show that one can approximate F0,F1,F2 by a random- ized algorithm using logarithmic space. On the other hand, approximately computing Fk for k ≥ 6 requires space of order nΩ(1). This lower bound was later shown to also hold for all k ≥ 3 [BYJKS04], even for multiple
110
pass algorithms [CKS03], thus giving essentially a complete picture of the complexity of computing frequency moments.
All of these lower bounds work by showing that an efficient algorithm for computing Fk leads to an efficient protocol for a promise version of DIS- JOINTNESS in the number-in-the-hand model of multiparty communication complexity, and then showing lower bounds on this communication problem. We will now sketch how this reduction works.
Let us first see how to get a lower bound on the space required to compute F∞ from the two-party lower bound on DISJOINTNESS. This case is easier and will illustrate the basic idea. Say that we have a streaming algorithm which uses space c and which for any stream of at most 2n elements outputs a value in (1±1/4)F∞ with probability at least 2/3. We will use this streaming algorithm to construct a randomized protocol for disjointness using c bits of communication and success probability at least 2/3.
On input x ∈ {0,1}n, Alice forms a string ax consisting of the indices where x has a one. Bob does the same with y to create ay. Alice then runs the streaming algorithm on ax and sends the contents of the memory to Bob with c bits of communication. Bob finishes the computation of the streaming algorithm on ay. If the computation of F∞ returns a value of at most 5/4, then they say that the strings do not intersect, otherwise that they do. Notice that if the strings do not intersect the true value of F∞ will be one, whereas if they do intersect, it will be at least two. Thus by the suc- cess guarantee of the streaming algorithm, the communication protocol will be correct with probability at least 2/3. Finally, as Kalyanasundaram and Schnitger [KS87] have shown that any randomized protocol for disjointness requires communication Ω(n) it follows that any streaming algorithm ap- proximating F∞ with high probability requires memory linear in the length of the stream. Notice that the algorithm we constructed was in fact one- way; as the Kalyanasundaram and Schnitger lower bound works for general protocols, this shows that even streaming algorithms which make multiple passes over the data in the same order must use linear space.
The general case reduces computing Fk to a promise version of disjoint- ness, UNIQUE DISJOINTNESS, in the n1/k-party number-in-hand model. This problem is defined as UDISJl(x1,…,xl) = T if xi ∩xj = ∅ for all i ̸= j and F if x1, . . . , xl intersect in exactly one element. Otherwise the problem is undefined.
Theorem 103 (Alon, Matias, and Szegedy [AMS99]) Fix a natural num- ber k. Suppose there is a randomized streaming algorithm which for ev- ery stream of length n uses c(n) bits of memory and outputs a value in
111
[ 9 Fk, 11Fk] with probability at least 2/3. Then in the n1/k-party number-in- 10 10
hand model
R(UDISJn1/k ) = O(c(n)n1/k )
Proof We will assume that the total number of ones in the inputs to the
players is exactly n. As in the F∞ case described above, each player converts
her input xi into a stream ai consisting of the indices where xi has a one.
The first player then runs the streaming algorithm for Fk on a1 and com-
municates with c bits the contents of the memory to the second player, who
does the same thing and reports the contents of the memory to the third
player, etc. The last player sees the final output of the streaming algorithm
and says that the strings do intersect if the answer is at least 12 n, and other- 10
wise says that they do not intersect. The total communication is thus cn1/k and is one-way. Notice that if the inputs are mutually disjoint, then Fk is exactly n. On the other hand, if the sets uniquely intersect, then Fk will be n+n−n1/k ≥3n/2.
The best known results on the number-in-the-hand multiparty complex- ity of disjointness show
Theorem 104 (Chakrabarti, Khot, and Sun [CKS03]) In the number- in-the-hand multiparty model, s players must communicate at least Ω(n/s log(s)) bits to determine if their sets from the universe [n] are mutually disjoint or uniquely intersecting with probability at least 2/3.
By the above reduction, this theorem has the following application:
Theorem 105 Any streaming algorithm which computes Fk within a multi- plicative factor of 1.1 with high probability must use space at least Ω(n1−2/k / log n), even if a constant number of passes are permitted.
9.2 NOF upper bounds
A major open problem is to show a lower bound in the number-on-the- forehead model of multiparty communication complexity which remains non- trivial for more than logn players. We have surveyed the existing lower bound techniques in the number-on-the-forehead model, and also seen that they are inherently limited to bounds of the form n/2k for k-many players. The results we discuss in this section both give a lot of motivation to showing lower bounds for more than log n players, and show that this is not possible for a class of well studied functions.
112
9.2.1 Protocol of Grolmusz
Let f : {0,1}n → {0,1} be a symmetric function. In other words, f(x) = f(y) whenever x and y have the same number of ones. Let x1,…,xk ∈ {0,1}n be the inputs to the k-players. We will think of the input as being described by a k-by-n matrix X whose ith row is xi. The key step in the protocol of Grolmusz is the following lemma:
Lemma 106 (Grolmusz [Gro94]) Let f be a symmetric function. Sup- pose the players know that some string r ∈ {0,1}k does not appear in the input matrix X. Then they can evaluate f(x1 ∧…∧xk) with klogn bits of communication.
Proof Notice that if the players can count the number of all-one columns in X then they can compute f. By rearranging the rows of X as necessary, we may assume that the missing column r is of the form 0l1k−l where l ∈ {1, . . . , k}. If l = 0 then the all-one column does not appear, and the players can immediately evaluate f.
More generally, let ei = 0i1k−i for i ∈ {0, . . . , k}. Thus the players want to count the number of times e0 appears as a column of X. Let Ei be the number of times the string ei appears as a column of X.
Although the first player cannot distinguish between a column of the form e0 or e1 as he does not see the first bit, he can exactly compute E0 + E1. Player 1 announces this number with log n bits. Similarly, player 2 announces E1 + E2. The players continue this way until they reach player l, who will announce El−1 as by assumption el does not appear as a column of X. With this knowledge, the players can then solve for E0 and evaluate f.
Theorem 107 (Grolmusz [Gro94]) Let f be a symmetric function. Then 2 n
Dk(f(x1 ∧…∧xk))≤k log(n) 2k−1 −1 .
Proof Thefirstplayerwillplayaspecialroleintheprotocol.He(mentally)
partitions the input matrix X into n many blocks of columns of size 2k−1 −1
2k−1 − 1. By counting, in each of these blocks of columns, there is some k − 1 bit string which does not appear, and can be identified by the first player. The first player announces these strings, and then the players perform the protocol given in the lemma. The total communication is
2 n k log(n) 2k−1−1 .
113
Remark 108 In the special case where f is the parity function, this com- munication can be reduced to
n k 2k−1−1
as in the lemma the players do not need to say Ei + Ei+1 but just the parity of this number.
Remark 109 Notice that the protocol of Grolmusz is nearly simultaneous, but not quite as the first player must announce the missing columns to the other players. Babai et al. [BGKL03] have shown that any function f(x1 ∧ … ∧ xk) for symmetric f indeed has a simultaneous protocol with O(logO(1)(n)) bits of communication whenever the number of players is larger than log n + 1.
9.2.2 Protocol for small circuits
One of the principal motivations for studying multiparty number-on-the- forehead communication complexity is that lower bounds in this model imply circuit complexity lower bounds. A key observation in this connection is due to Håstad and Goldmann.
Lemma 110 (Håstad and Goldmann [HG91]) Suppose that a function f can be computed by a depth-2 circuit whose top gate is an arbitrary symmet- ric function of fan-in s and whose bottom gates compute arbitrary functions of fan-in at most k − 1. Then, under any partition of the input variables, the k-party number-on-the-forehead complexity of f is at most k log(s). Fur- thermore, this can be achieved by a simultaneous protocol.
Proof As each bottom gate has fan-in at most k − 1, under any parti- tion of the input variables, there is some player who sees the entire input to this gate. By a scheme arranged beforehand, the players partition these gates among themselves so that each gate is computed by some player. Each player then announces the number of gates assigned to him which evaluate to true. This takes log s bits of communication. Once the players know the total number of bottom gates which evaluate to true, they can compute f. The total communication is k log(s).
114
The functions which can be computed by quasipolynomial size depth-2 circuits with a symmetric top gate and bottom gates of polylogarithmic size fan-in is a surprisingly rich class. Indeed, Allender [All89] shows that this class can compute all of AC0. Further work by Yao [Yao90] shows that the probabilistic version of this class can compute all of ACC0 and Beigel and Tarui [BT94] improve this to a deterministic simulation. We record this statement for reference.
Theorem 111 (Beigel and Tarui) Any language in ACC0 can be com- puted by a depth-2 circuit of size 2logO(1)(n) with a symmetric gate at the top and AND gates of fan-in logO(1) n at the bottom.
As a consequence, showing that a function f requires super-polylogarithmic communication for super-polylogarithmic many players in the simultaneous number-on-the-forehead model will show that f is not in ACC0. We cur- rently do not know of any explicit function which is outside of ACC0.
115
Acknowledgements
We would like to thank Eitan Bachmat, Harry Buhrman, Arkadev Chat- topadhyay, Nati Linial, Gideon Schechtman, Sasha Sherstov, Ronald de Wolf, and the anonymous referee for many helpful comments which improved this survey.
116
Bibliography
[AA05] [AKM+ 06]
[All89]
[Alo03] [Alo09]
[AMS99]
[AN06]
[AS89] [AUY83]
S. Aaronson and A. Ambainis. Quantum search of spatial re- gions. Theory of Computing, 1:47–79, 2005.
N. Alon, Y. Kohayakawa, C. Mauduit, C. Moreira, and V. Rödl. Measures of pseudorandomness for finite sequences: minimal values. Combinatorics, Probability, and Computing, 15:1–29, 2006.
E. Allender. A note on the power of threshold circuits. In Pro- ceedings of the 30th IEEE Symposium on Foundations of Com- puter Science, pages 580–584, 1989.
N. Alon. Problems and results in extremal combinatorics, part i. Discrete Mathematics, 273:31–53, 2003.
N. Alon. Perturbed identity matrices have high rank: proof and applications. Combinatorics, Probability, and Computing, 18:3–15, 2009.
N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137–147, 1999.
N. Alon and A. Naor. Approximating the cut-norm via Grothendieck’s inequality. SIAM Journal on Computing, 35:787–803, 2006.
N. Alon and P. Seymour. A counterexample to the rank-coloring conjecture. Journal of Graph Theory, 13(4):523–525, 1989.
A. Aho, J. Ullman, and M. Yannakakis. On notions of informa- tion transfer in VLSI circuits. In Proceedings of the 15th ACM
117
[AW09]
[BBC+ 01]
[BCW98]
[BDPW07]
[BES02]
[BFS86]
[BGKL03]
[BHN08] [BNS89]
Symposium on the Theory of Computing, pages 133–139. ACM, 1983.
S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computing Theory, 1, 2009.
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. Earlier version in FOCS’98.
H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 63–68. ACM, 1998.
P. Beame, M. David, T. Pitassi, and P. Woelfel. Separating deterministic from randomized nof multiparty communication complexity. In Proceedings of the 34th International Colloquium On Automata, Languages and Programming, Lecture Notes in Computer Science. Springer-Verlag, 2007.
S. Ben-David, N. Eiron, and H. Simon. Limitations of learning via embeddings in Euclidean half spaces. Journal of Machine Learning Research, 3:441–461, 2002.
L. Babai, P. Frankl, and J. Simon. Complexity classes in com- munication complexity theory. In Proceedings of the 27th IEEE Symposium on Foundations of Computer Science. IEEE, 1986.
L. Babai, A. Gál, P. Kimmel, and S. Lokam. Simultaneous messages vs. communication. SIAM Journal on Computing, 33(1):137–166, 2003.
P. Beame and D. Huynh-Ngoc. Multiparty communication com- plexity of AC0. Technical Report TR-08-082, ECCC, 2008.
L. Babai, N. Nisan, and M. Szegedy. Multiparty protocols and Logspace-hard pseudorandom sequences. In Proceedings of the 21st ACM Symposium on the Theory of Computing, pages 1–11. ACM, 1989.
118
[BPS06] P. Beame, T. Pitassi, and N. Segerlind. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity. SIAM Journal on Computing, 37(3):845–869, 2006.
[BPSW06] P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson. A strong direct product lemma for corruption and the NOF complexity of disjointness. Computational Complexity, 15(4):391–432, 2006.
[BT94] R. Beigel and J. Tarui. On ACC. Computational Complexity, 4:350–366, 1994.
[Buh07] Harry Buhrman, December 2007. Personal communication.
[BVW07] H. Buhrman, N. Vereshchagin, and R. de Wolf. On computation and communication with small bias. In Proceedings of the 22nd IEEE Conference on Computational Complexity, pages 24–32. IEEE, 2007.
[BW01] H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th IEEE Con- ference on Computational Complexity, pages 120–130, 2001.
[BW02] H. Buhrman and R. de Wolf. Complexity measures and deci- sion tree complexity: A survey. Theoretical Computer Science, 288:21–43, 2002.
[BYJKS04] Z. Bar-Yossef, T. Jayram, R. Kumar, and D. Sivakumar. In- formation statistics approach to data stream and communica- tion complexity. Journal of Computer and System Sciences, 68(4):702–732, 2004.
[CA08] A. Chattopadhyay and A. Ada. Multiparty communication com- plexity of disjointness. Technical Report TR-08-002, ECCC, 2008.
[Cha07] A. Chattopadhyay. Discrepancy and the power of bottom fan- in depth-three circuits. In Proceedings of the 48th IEEE Sym- posium on Foundations of Computer Science, pages 449–458. IEEE, 2007.
[Cha08] A. Chattopadhyay. Circuits, Communication, and Polynomials. PhD thesis, McGill University, 2008.
119
[CHSH69]
[Chu90] [CKS03]
[DKLR08]
[DPV08]
[Faj88] [FG05]
[FK99] [For02]
[Gro94]
[GW95]
J. Clauser, M. Horne, A. Shimony, and R. Holt. Proposed ex- periment to test local hidden-variable theories. Physical Review Letters, 23(15):880–884, 1969.
F. Chung. Quasi-random classes of hypergraphs. Random Struc- tures and Algorithms, 1:363–382, 1990.
A. Chakrabarti, S. Khot, and X. Sun. Near-optimal lower bounds on the multi-party communication complexity of set- disjointness. In Proceedings of the 18th IEEE Conference on Computational Complexity. IEEE, 2003.
J. Degorre, M. Kaplan, S. Laplante, and J. Roland. The com- munication complexity of non-signaling distributions. Technical Report 0804.4859, arXiv, 2008.
M. David, T. Pitassi, and E. Viola. Improved separations be- tween nondeterministic and randomized multiparty communica- tion. In APPROX-RANDOM, volume 5171 of Lecture Notes in Computer Science, pages 371–384. Springer, 2008.
S. Fajtlowicz. On conjectures of graffiti. Discrete Mathematics, 72:113–118, 1988.
J. Ford and A. Gál. Hadamard tensors and lower bounds on multiparty communication complexity. In Proceedings of the 32th International Colloquium On Automata, Languages and Programming, pages 1163–1175, 2005.
A. Frieze and R. Kannan. Quick approximation to matrices and applications. Combinatorica, 19:175–220, 1999.
J. Forster. A linear lower bound on the unbounded error prob- abilistic communication complexity. Journal of Computer and System Sciences, 65:612–625, 2002.
V. Grolmusz. The BNS lower bound for multi-party protocols is nearly optimal. Information and computation, 112(1):51–54, 1994.
M. Goemans and D. Williamson. Improved approximation al- gorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM, 42:1115–1145, 1995.
120
[Hås90] [HG91] [Jam87] [JKS03]
[JL01]
[JR93] [KKN95]
[Kla01]
[Kla03]
[KLO96]
[KN97] [Kra96]
J. Håstad. Tensorrank is NP-complete. Journal of Algorithms, 11:644–654, 1990.
J. Håstad and M. Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1:113–129, 1991.
G. J. O. Jameson. Summing and nuclear norms in banach space theory. Cambridge University Press, 1987.
T. Jayram, R. Kumar, and D. Sivakumar. Two applications of information complexity. In Proceedings of the 35th ACM Sympo- sium on the Theory of Computing, pages 673–682. ACM, 2003.
W. Johnson and J. Lindenstrauss. Basic concepts in the geom- etry of Banach spaces. In Handbook of the geometry of Banach spaces, Vol. I, pages 1–84. North-Holland, Amsterdam, 2001.
T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on Computing, 22:1117–1141, 1993.
M. Karchmer, E. Kushilevitz, and N. Nisan. Fractional cov- ers and communication complexity. SIAM Journal on Discrete Mathematics, 8(1):76–92, 1995.
H. Klauck. Lower bounds for quantum communication complex- ity. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE, 2001.
H. Klauck. Rectangle size bounds and threshold covers in com- munication complexity. In Proceedings of the 18th IEEE Con- ference on Computational Complexity. IEEE, 2003.
E. Kushilevitz, N. Linial, and R. Ostrovsky. The linear array conjecture of communication complexity is false. In Proceedings of the 28th ACM Symposium on the Theory of Computing. ACM, 1996.
E. Kushilevitz and N. Nisan. Communication Complexity. Cam- bridge University Press, 1997.
M. Krause. Geometric arguments yield better bounds for thresh- old circuits and distributed computing. Theoretical Computer Science, 156:99–117, 1996.
121
[Kre95] [Kri79] [KS87]
[KS07]
[LMSS07]
[Lov75] [Lov90]
[LS88]
[LS08]
[LS09a]
[LS09b]
I. Kremer. Quantum communication. Technical report, Hebrew University of Jerusalem, 1995.
J. Krivine. Constantes de Grothendieck et fonctions de type positif sur les sphères. Adv. Math., 31:16–30, 1979.
B. Kalyanasundaram and G. Schnitger. The probabilistic com- munication complexity of set intersection. In Proceedings of the 2nd Annual Conference on Structure in Complexity Theory, pages 41–49, 1987.
A. Klivans and A. Sherstov. A lower bound for agnostically learning disjunctions. In Proceedings of the 20th Conference on Learning Theory, 2007.
N. Linial, S. Mendelson, G. Schechtman, and A. Shraib- man. Complexity measures of sign matrices. Combinatorica, 27(4):439–463, 2007.
L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383–390, 1975.
L. Lovász. Communication complexity: A survey. In B. Korte, L. Lovász, H. Prömel, and A. Schrijver, editors, Paths, flows, and VLSI-layout, pages 235–265. Springer-Verlag, 1990.
L. Lovász and M. Saks. Möbius functions and communication complexity. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, pages 81–90. IEEE, 1988.
T. Lee and A. Shraibman. An approximation algorithm for approximation rank. In Proceedings of the 24th IEEE Confer- ence on Computational Complexity, pages 351–357. IEEE, 2008. arXiv:0809.2093 [cs.CC].
T. Lee and A. Shraibman. Disjointness is hard in the multi- party number-on-the-forehead model. Computational Complex- ity, 18(2):309–336, 2009.
N. Linial and A. Shraibman. Learning complexity versus com- munication complexity. Combinatorics, Probability, and Com- puting, 18:227–245, 2009.
122
[LS09c]
[LSŠ08]
[LSS09]
[LSZ09] [LY94]
[MS82]
[NC00] [New91]
[NS94] [Nuf76] [NW95] [Orl77]
N. Linial and A. Shraibman. Lower bounds in communication complexity based on factorization norms. Random Structures and Algorithms, 34:368–394, 2009.
T. Lee, A. Shraibman, and R. Špalek. A direct product theorem for discrepancy. In Proceedings of the 23rd IEEE Conference on Computational Complexity, pages 71–80. IEEE, 2008.
T. Lee, G. Schechtman, and A. Shraibman. Lower bounds on quantum multiparty communication complexity. In Proceed- ings of the 24th IEEE Conference on Computational Complexity, pages 254–262. IEEE, 2009.
T. Lee, A. Shraibman, and S. Zhang. Composition theorems in communication complexity. Manuscript, 2009.
C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960–981, 1994.
K. Mehlhorn and E. Schmidt. Las Vegas is better than deter- minism in VLSI and distributed computing. In Proceedings of the 14th ACM Symposium on the Theory of Computing, pages 330–337. ACM, 1982.
M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
I. Newman. Private versus common random bits in commu- nication complexity. Information Processing Letters, 39:67–71, 1991.
N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301–313, 1994.
C. van Nuffelen. A bound for the chromatic number of a graph. American Mathematical Monthly, 83:265–266, 1976.
N. Nisan and A. Wigderson. A note on rank vs. communication complexity. Combinatorica, 15(4):557–566, 1995.
J. Orlin. Contentment in graph theory: covering graphs with cliques. Indigationes Mathematicae, 80:406–424, 1977.
123
[Pat92]
[PS86]
[Raz92a]
[Raz92b] [Raz95] [Raz99]
[Raz00] [Raz03] [Ree91] [RS95] [RS08]
[Sch11]
R. Paturi. On the degree of polynomials that approximate sym- metric Boolean functions (preliminary version). In Proceedings of the 24th ACM Symposium on the Theory of Computing, pages 468–474. ACM, 1992.
R. Paturi and J. Simon. Probabilistic communication complex- ity. Journal of Computer and System Sciences, 33(1):106–123, 1986.
A. Razborov. On submodular complexity measures. In M. Pa- terson, editor, Boolean function complexity, volume 169 of Lon- don Math. Soc. Lecture Notes Series, pages 76–83. Cambridge University Press, 1992.
A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106:385–390, 1992.
R. Raz. Fourier analysis for probabilistic communication com- plexity. Computational Complexity, 5(3/4):205–221, 1995.
R. Raz. Exponential separation of quantum and classical com- munication complexity. In Proceedings of the 31st ACM Sympo- sium on the Theory of Computing, pages 358–367. ACM, 1999.
R. Raz. The BNS-Chung criterion for multi-party communica- tion complexity. Computational Complexity, 9(2):113–122, 2000.
A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145–159, 2003.
J. Reeds. A new lower bound on the real Grothendieck constant. Available at http://www.dtc.umn.edu/~reedsj, 1991.
R. Raz and B. Spieker. On the log rank conjecture in commu- nication complexity. Combinatorica, 15(4):567–588, 1995.
A. Razborov and A. Sherstov. The sign rank of AC0. In Proceed- ings of the 49th IEEE Symposium on Foundations of Computer Science, pages 57–66. IEEE, 2008.
I. Schur. Bemerkungen zur Theorie beschränkten Bilinearformen mit unendlich vielen Veränderlichen. J. Reine Angew. Math., 140:1–28, 1911.
124
[Sha03] [She08a] [She08b] [She08c]
[She08d]
[She09] [SZ09a] [SZ09b]
[Tsi87]
[Ung08] [Vav07] [VB96] [Yan91]
R. Shaltiel. Towards proving strong direct product theorems. Computational Complexity, 12(1–2):1–22, 2003.
A. Sherstov. Communication lower bounds using dual polyno- mials. Bulletin of the EATCS, 95:59–93, 2008.
A. Sherstov. Halfspace matrices. Computational Complexity, 17(2):149–178, 2008.
A. Sherstov. The pattern matrix method for lower bounds on quantum communication. In Proceedings of the 40th ACM Sym- posium on the Theory of Computing, pages 85–94. ACM, 2008.
A. Sherstov. The unbounded-error communication complexity of symmetric functions. In Proceedings of the 49th IEEE Sym- posium on Foundations of Computer Science. IEEE, 2008.
A. Sherstov. Separating AC0 from depth-2 majority circuits. SIAM Journal on Computing, 38(6):2113–2129, 2009.
Y. Shi and Z. Zhang. Communication complexities of XOR func- tions. Quantum information and computation, 2009.
Y. Shi and Y. Zhu. Quantum communication complexity of block-composed functions. Quantum information and computa- tion, 9(5,6):444–460, 2009.
B. Tsirelson. Quantum analouges of the Bell inequalities: the case of two spatially separated domains. Journal of Soviet Math- ematics, 36:557–570, 1987.
F. Unger. Noise in classical and quantum computation and non- locality. PhD thesis, University of Amsterdam, 2008.
S. Vavasis. On the complexity of nonnegative matrix factoriza- tion. Technical Report arXiv:0708.4149 [cs.NA], ArXiv, 2007.
L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38:49–95, 1996.
M. Yannakakis. Expressing combinatorial optimization prob- lems by linear programs. Journal of Computer and System Sci- ences, 43(3):441–466, 1991.
125
[Yao79]
[Yao83]
[Yao90]
[Yao93]
A. Yao. Some complexity questions related to distributive com- puting. In Proceedings of the 11th ACM Symposium on the The- ory of Computing, pages 209–213. ACM, 1979.
A. Yao. Lower bounds by probabilistic arguments. In Proceed- ings of the 24th IEEE Symposium on Foundations of Computer Science, pages 420–428, 1983.
A. Yao. On ACC and threshold circuits. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 619–627. IEEE, 1990.
A. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, pages 352–360. IEEE, 1993.
126