Separating the k-party communication complexity hierarchy:

an application of the Zarankiewicz problem Preliminary Draft

Thomas P. Hayes^{∗} Department of Mathematics University of Chicago

February 24, 2003

Abstract

For every positive integer k, we construct an explicit family of functions f : {0, 1}^{n} → {0, 1} which has (k + 1)-party communication complexity O(k) under every partition of the input bits into k + 1 parts of equal size, and k-party communication complexity Ω (\frac{n}{k^{4}2^{k}} ) under every partition of the input bits into k parts. This improves an earlier hierarchy theorem due to V. Grolmusz.

Our construction relies on known explicit constructions for a famous open problem of Zarankiewicz: find the maximum number of edges in a graph on n vertices which does not contain K_{s,t} as a subgraph.

The “Number on the Forehead” model of multiparty communication complexity was introduced by Chandra, Furst, and Lipton [2]. In this model, k players, P_{1}, …, P_{k}, use a communication protocol to collaboratively evaluate a function f(x_{1}, …, x_{k}) on a particular input. The components x_{i} of the input are written on the forehead of player P_{i}, so that each player sees the values of all components except his own. The players then take turns broadcasting strings of bits according to their protocol, at the end of which, all players must know the value of f(x_{1}, …, x_{k}).

∗Email: hayest@math.uchicago.edu.

We will show that there is a real difference in the computational power of k players and k + 1 players in this model, by constructing explicit functions which are easy for k + 1 players, and hard for k players. However, before we can begin to discuss this construction, we must first specify how a function of k input strings x_{1}, …, x_{k} is to be viewed as a function of k + 1 input strings.

We think of f as a boolean function f : {0, 1}^{n} → {0, 1}, whose n input bits are partitioned into k parts, and each part of the partition is assigned to a player, so that every bit is seen by exactly k − 1 players. The communication complexity of a function may vary greatly depending on the partition chosen. Such partition models have already been studied (cf. Kushilevitz and Nisan [7, Ch. 6–7]). Two different methods for defining the communication complexity in this context are:

• Worst-case partition: All possible partitions of the input into k parts are considered, and the complexity of f is the maximum of the various complexities.

• Best-case equipartition: All equipartitions of the input (partitions into k parts whose sizes differ by at most one) are considered, and the complexity of f is the minimum of the various complexities. (If there were no restriction on the sizes of the parts, the complexity would always be zero.)

Our separation result for the multiparty communication complexity hierarchy holds in the strongest possible sense: our lower bound holds for every equipartition (even the best), and our upper bound holds for every partition (even the worst).

Theorem 1 Let k ≥ 2. There exists an explicit family of functions f : {0, 1}^{n} → {0, 1} such that the (k + 1)-party communication complexity of f is O(k) under any partition, while the k-party communication complexity is Ω (\frac{n}{k^{4}2^{k}} ) under any equipartition.

If k is fixed and n → ∞, then this result is optimal up to constant factors:

Corollary 2 For every fixed k ≥ 2, there exists an explicit family of functions having k-party communication complexity Ω(n) under any equipartition of the inputs, and (k + 1)-party communication complexity O(1) under any partition of the inputs.

Our results were inspired by the following result of Grolmusz [5], and by its proof.

Proposition 3 (Grolmusz [5]) Let k and k′ be fixed constants, such that there exists a prime k < p ≤ k′. There exists an explicit family of functions having k-party communication complexity Ω(n) under some equipartition of the inputs, and k′-party communication complexity O(1) under any partition of the inputs.

We have improved this by removing the condition k < p ≤ k′, and by extending the lower bound to hold for for arbitary equipartitions.

1 Preliminaries

In this section, we summarize the definitions and familiar results which form the building blocks of our construction. The family of functions we will construct is defined using a particular class of hypergraphs, which is in turn defined using Zarankiewicz graphs.

Definition 4 Let H be a hypergraph. The function GIP_{H} : {0, 1}^{V (H)} → {0, 1} is defined by

GIP_{H}(x⃗) := ∑_{e∈E(H)} ∏_{v∈e} x_{v} (mod 2),

and is called the generalized inner product over H.

Remark. The mapping H ↦ GIP_{H} defines a bijection between the set of hypergraphs with vertex set V and the set of all functions f : V → {0, 1}. Indeed, the edges of H correspond to the monomial terms when GIP_{H} is written as a multilinear polynomial over GF (2).

The following proposition is due to Hastad? Smolensky? and was used for one of the earliest applications of communication games to circuit complexity.

Proposition 5 If the largest edge in H contains k − 1 vertices, then there is a k-party communication protocol evaluating GIP_{H} using at most k bits of communication.

Proof: By definition GIP_{H} is a polynomial of degree at most k − 1 over GF (2). For each monomial, there exists a player who can evaluate it. Assign each monomial to the lowest index player who can evaluate it. Each player evaluates his assigned monomials, then takes their mod 2 sum, adds it to the previous communicated bit, if any, and broadcasts this bit as his message. □

When H is a perfect matching, GIP_{H} is the usual inner product over GF (2). More generally, when the edges of H are pairwise disjoint and of size k, GIP_{H} = GIP_{k} is the generalized inner product function of Babai, Nisan and Szegedy [1]. These authors showed showed that C_{k}(GIP_{k}) = Ω(n/4^{k}). Their result was improved by Chung and Tetali [3] to:

Proposition 6 Let H be a k-uniform perfect matching on n vertices. Then

C_{k}(GIP_{H}) = Ω (\frac{n}{k2^{k}} ) .

Remark. A nearly-matching upper bound of O(n/2^{k}) is due to Grolmusz [4].

Definition 7 If H is a hypergraph, and S ⊆ V (H) is a set of vertices, then the sub-hypergraph of H induced by S is the hypergraph G with vertex set S and edge set {e ∈ E(H) | e ⊆ S}.

Proposition 8 If G is a vertex-induced sub-hypergraph of H, as defined above, then C(GIP_{H}) ≥ C(GIP_{G}).

Proof: Observe that GIP_{G} is the restriction of GIP_{H} induced by setting x_{v} = 0 for all v ∈ V (H) − V (G). The result is immediate. □

We will use graphs with the following property in our construction.

Definition 9 Let G be a graph on n vertices, and let c > 0. We say G is c-interconnected if, for every pair of disjoint sets S_{1}, S_{2} ⊂ V such that |S_{1}| , |S_{2}| ≥ c, there exists at least one edge from S_{1} to S_{2}. In other words, the complement of G contains no subgraph isomorphic to K_{c,c}, the complete c by c bipartite graph.

Remark. Finding the minimum number of edges in a c-interconnectedgraph is a special case of a notoriously difficult question called the Zarankiewicz problem. This problem is normally phrased as, for positive integers s, t, to find the maximum number of edges in a graph containing no subgraph isomorphic to K_{s,t}. Our question is the complemented version of the case s = t = c. An explicit construction for the Zarankiewicz problem in the case s ≥ t! was found by Kollar, Ronyai and Szabo [?], using sophisticated methods from algebraic geometry. For the case s = t = c ≥ 3, even the correct order of magnitude for the right answer is not known, and no explicit constructions approach the naive probabilistic bound below (due to Smolensky??).

Proposition 10 Let G be a random graph on n vertices, with each possible edge included with probability p > 0, independent of all others. Then, with probability 1 − o(1/), G is (8 ln(n)/p + 1)-interconnected.

We omit the proof, which is an easy counting argument.

For explicit constructions of c-interconnected graphs, we rely on explicit constructions of expanders. The best possible expanders are Ramanujan graphs (defined below). Explicit constructions of these are due to Lubotzky, Philips and Sarnak [6] and Margulis [?].

Definition 11 Let G be a d-regular graph on n vertices. Let d = λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n} be the eigenvalues of G. G is called a Ramanujan graph if all eigenvalues of G are in the set \{−d, d\} ∪ [−2\sqrt{d − 1}, 2\sqrt{d − 1}].

Remark. When G is connected and non-bipartite, it has a single largest eigenvalue in absolute value, so in this case, the n − 1 other eigenvalues lie in [−2\sqrt{d − 1}, 2\sqrt{d − 1}].

The following lemma, due to N. Alon, states that connected non-bipartite connected Ramanujan graphs are highly interconnected. We include a proof for completeness.

Lemma 12 Let G be a d-regular connected non-bipartite Ramanujan graph on n vertices. Then G is \frac{2n}{\sqrt{d+1}}-interconnected.

Proof: Let c = \frac{2n}{\sqrt{d+1}}, and let S, T ⊂ V (G) be disjoint sets of vertices such that |S|, |T | ≥ c. Let x_{S} (resp. x_{T}) be the characteristic vector of the set S (resp. T), with respect to some labelling of V (G). Let A be the adjacency matrix of G, with respect to the same labelling. Then we easily see m(S, T) = x_{S}^{t}Ax_{T}.

Let d = λ_{1} > λ_{2} ≥ λ_{3} ≥ ⋯ ≥ λ_{n} be the eigenvalues of G, and let v_{1}, …, v_{n} be a corresponding orthonormal basis of eigenvectors. Let us express x_{S} = ∑_{i=1}^{n} α_{i}v_{i} and x_{T} = ∑_{i=1}^{n} β_{i}v_{i} in this basis. With this notation, m(S, T) = x_{S}^{t}Ax_{T} = ∑_{i=1}^{n} α_{i}β_{i}λ_{i}.

It is easy to see that v_{1} = (1, 1 …, 1)/\sqrt{n}, from which we observe that α_{1} = |S|/\sqrt{n} and β_{1} = |T |/\sqrt{n}. We also note that |S| = ∥x_{S}∥^{2} = ∑_{i=1}^{n} α_{i}^{2} and that |T | = ∥x_{T}∥^{2} = ∑_{i=1}^{n} β_{i}^{2}.

Substituting, we have

|m(S, T) − \frac{|S||T |d}{n}| = |∑_{i=2}^{n} α_{i}β_{i}λ_{i}| ≤ ∑_{i=2}^{n} |α_{i}β_{i}|2\sqrt{d − 1}

By the Cauchy-Schwarz inequality,

(∑_{i=2}^{n} |α_{i}β_{i}|)^{2} ≤ ∑_{i=1}^{n} α_{i}^{2} ∑_{i=1}^{n} β_{i}^{2} = |S||T |.

It follows that

m(S, T) ≥ \frac{|S||T |d}{n} − 2\sqrt{|S||T |(d − 1)}
= \sqrt{|S||T |(d − 1)} (\frac{\sqrt{|S||T |}d}{n\sqrt{d − 1}} − 2)

≥ \sqrt{|S||T |(d − 1)} (\frac{c\sqrt{d + 1}}{n} − 2) .

By the definition of c, this last term is positive. Hence m(S, T) > 0, proving that G is c-interconnected. □

Remark. Alon used the same analysis to give a somewhat stronger result, namely that, for somewhat larger sets S and T, the density of edges between S and T is always approximately the same as the density of edges in the entire graph G.

2 Results

The next two lemmas present surprising properties of c-interconnected graphs. These will be used in the proof of Theorem 1, but may also be interesting in their own right.

First, we find it convenient to generalize the concept of c-interconnectedness:

Definition 13 Let c be a positive integer. We say a graph G = (V, E) is cstarry if the following holds. Let S_{1}, S_{2}, …, S_{m} ⊂ V be pairwise disjoint sets, each of size at least c. Then there exist vertices v_{1} ∈ S_{1}, v_{2} ∈ S_{2}, …, v_{m} ∈ S_{m} that form a star in G, i.e. there is an index 1 ≤ j ≤ m such that for all i ≠ j, (v_{j}, v_{i}) ∈ E.

Remark. Every c-starry graph is c-interconnected, since we can let m = 2 in Definition 13. Surprisingly, the converse is also true:

Lemma 14 Every c-interconnected graph G is c-starry.

Proof: Let G = (V, E) and let S_{1}, S_{2}, …, S_{m} ⊂ V be pairwise disjoint sets, each of size at least c.

For 1 ≤ i ≤ m, let T_{i} = V \ S_{i} \ Γ(S_{i}) = {v ∈ V \ S_{i} | ∀w ∈ S_{i}, (v, w) ∉ E}. By hypothesis, |T_{i}| < c, since G contains no edge from T_{i} to S_{i}. Hence

|∪_{i}T_{i}| ≤ (c − 1)m < cm = |∪_{i}S_{i}| ,

so by the pigeonhole principle, there exists an element v_{j} ∈ S_{j} \(∪_{i}T_{i}), which is the center of the desired star. □

The next lemma is incidental to our main result, but is closely related to the previous lemma, and possibly of independent interest.

Lemma 15 Let G = (V, E) be a c-interconnected graph. Let T be any tree on m vertices. Let V (T) = {t_{1}, …, t_{m}}. Let S_{1}, S_{2}, …, S_{m} ⊂ V be pairwise disjoint sets such that for all i, |S_{i}| ≥ dc, where d is the maximum degree of T. Then there exist vertices v_{1} ∈ S_{1}, v_{2} ∈ S_{2}, …, v_{m} ∈ S_{m} such that if (t_{i}, t_{j}) ∈ E(T), then (v_{i}, v_{j}) ∈ E(G).

The proof is a straightforward induction, which we omit. We are now ready to begin our construction.

Definition 16 Let G = (V, E) be a graph. We define the hypergraph of k-stars in G to be the k-uniform hypergraph on vertex set V, whose edges are all k-tuples in which at least one vertex is adjacent to the other k − 1.

Lemma 17 Let G = (V, E) be a c-interconnected regular graph of degree d on n vertices. Let H be the hypergraph of k-stars in G. Then, for any equipartition of V into k parts, there exists S ⊂ V, with |S| > \frac{n−kc}{kd}, such that the sub-hypergraph of H induced by S consists of pairwise disjoint edges, each of which intersects all k parts nontrivially.

Proof: We define S recursively. Initially, let S be empty. In each stage, apply Lemma 14 to find a star having one vertex in each set of the partition. Add these k vertices to S. Delete the k vertices, and all their neighbors, from G. Repeat, restricting the given partition to the remaining vertices of G.

After i stages, at most ikd vertices have been removed from G, which means each set in the partition remains at least size n/k − ikd. Since G is c-interconnected, Lemma 14 will apply as long as n/k − ikd ≥ c. Thus, the algorithm will run for at least (n − kc)/(k^{2}d) stages.

Because H is k-uniform, and at each stage we removed all neighbors of the k vertices added, the sub-hypergraph induced by S contains only one edge for each stage, and these are pairwise disjoint. □

Lemma 18 Let G = (V, E) be a c-interconnected regular graph of degree d on n vertices. Let H be the hypergraph of k-stars in G. Then, for any equipartition of the inputs into k parts,

C_{k}(GIP_{H}) = Ω (\frac{n − kc}{k^{2}d2^{k}}) .

But the k + 1-party communication complexity is at most k + 1, regardless of how the inputs are partitioned.

Proof: By Lemma 17, H contains a sub-hypergraph G of Ω (\frac{n−kc}{kd}) vertices, such that GIP_{G} is exactly the original GIP function of Babai, Nisan and Szegedy [1]. By Propositions 8 and 6,

C_{k}(GIP_{H}) ≥ C_{k}(GIP_{G}) = Ω (\frac{n − kc}{k^{2}d2^{k}})

The upper bound for k + 1 players follows directly from Proposition 10. □

Theorem 19 Let G be a Ramanujan graph of degree d ≈ 16k^{2}. Let H be the hypergraph of k-stars in G. Then for any partition of the inputs into k equal parts,

C_{k}(GIP_{H}) = Ω (\frac{n}{k^{4}2^{k}} ) .

But the k + 1-party communication complexity is at most k + 1, regardless of how the inputs are partitioned.

Proof: This follows from composing Lemmas 12 and 18. □

Theorem 19 implies Theorem 1.

3 Conclusions and Open Questions

Although it is intuitive that adding more players can reduce communication complexity, the amount gained is not clear. We have seen that, for O(1) players, adding just one player to the game can cause the communication complexity to plummet from Ω(n) to O(1); this is the most that could be hoped for. However, what if k is a non-constant function of n?

A simple counting argument shows that, for a randomly chosen boolean function of kn variables, the k-party communication complexity is Ω(n) with high probability, regardless of the dependence of k on n.

In stark contrast, no explicit family of boolean functions has been shown to have ω(log n) communication complexity for k = ω(log n) players. Even for weaker models of communication such as the Simultaneous Messages model (cf. [7]), no such construction is known. To narrow this gap even slightly is one of the major challenges in communication complexity theory today.

For the question of separating the k-party communication hierarchy, there is not even a non-constructive proof that the k-player versus (k + 1)-player separation extends beyond k = O(log n) players, in either the best-case or the worst-case partition models. An answer to this question would be most welcome.

References

[1] L. Babai, N. Nisan, and M. Szegedy. Multiparty Protocols, Pseudorandom Generators for Logspace and Time-Space Trade-offs. Journal of Computer and System Sciences 45 (1992) 204–232.

[2] A.K. Chandra, M.L. Furst, and R.J. Lipton. Multiparty Protocols. Proc. of the 15th ACM STOC (1983) 94–99.

[3] F.R.K. Chung and P. Tetali. Communication complexity and quasi randomness. SIAM J. Discrete Math. 6 (1993) 110–123.

[4] V. Grolmusz. The BNS Lower Bound for Multi-Party Protocols is Nearly Optimal. Information and Computation 112 (1994) 51–54.

[5] V. Grolmusz. Separating the Communication Complexities of MOD m and MOD p Circuits. Journal of Computer and System Sciences 51 (1995) 307–313.

[6] A. Lubotzky, R. Phillips, R., and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988) 261–277.

[7] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997.