# Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem.

The "Number on the Forehead" model of multiparty communication complexity was introduced by Chandra, Furst, and Lipton [4]. In this model, k players, [P.sub.1],..., [P.sub.k], use a communication protocol to collaboratively evaluate a function f ([x.sub.1],..., [x.sub.k]) on a particular input. The components [x.sub.i] of the input are written on the forehead of player [P.sub.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.sub.1],... ,[x.sub.k]).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.sub.1],..., [x.sub.k] is to be viewed as a function of k + 1 input strings.

We think of f as a boolean function f : [{0,1}.sup.n] [right arrow] {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 (see, for instance, Kushilevitz and Nisan [12, 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}.sup.n] [right arrow] {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 [OMEGA]{n/[k.sup.4][2.sup.k]) under any equipartition.

If k is fixed and n [right arrow] [infinity], then this result is optimal up to constant factors:

Corollary 2 For every fixed k [greater than or equal to] 2, there exists an explicit family of functions having k-party communication complexity [OMEGA](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 [8], and by its proof.

Proposition 3 (Grolmusz [8]) Let k and k' be fixed constants, such that there exists a prime k < p [less than or equal to] k'. There exists an explicit family of functions having k-party communication complexity [OMEGA](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 [less than or equal to] k', and by extending the lower bound to hold for for arbitrary equipartitions.

Related Work

A number of other "communication complexity hierarchies" have been studied previously--see, for instance [14, 2, 9]. These include, for instance, hierarchies based on the number of rounds, and on communication complexity versions of standard complexity theory hierarchies.

Duris et al. [6] recently proved a separation result in a two-player multi-partition model of communication complexity. Although their results have some interesting similarities to our own, there does not seem to be any real connection between the models.

Some unpublished notes of T. Pitassi [15] present substantially the same construction and results as ours. Although she has graciously conceded priority, we wish to acknowledge her independent discovery.

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.sub.H] : [{0,1}.sup.V(H)] [right arrow] {0,1} is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and is called the generalized inner product over H.

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

The following observation has long been known, and has appeared in many contexts.

Observation 5 If the largest edge in H contains k - 1 vertices, then there is a k-party communication protocol evaluating [GIP.sub.H] using at most k bits of communication.

Proof: By definition [GIP.sub.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.sub.H] is the usual inner product over GF(2). More generally, when the edges of H are pairwise disjoint and of size k, [GIP.sub.H] = [GIP.sub.k] is the generalized inner product function of Babai, Nisan and Szegedy [3]. These authors showed showed that [C.sub.k]([GIP.sub.k]) = [OMEGA](n/[4.sup.k]). Their result was improved by Chung and Tetali [5] to:

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

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Remark. A nearly-matching upper bound of O(n/[2.sub.k]) is due to Grolmusz [7].

Definition 7 If H is a hypergraph, and S [subset or equal to] V (H) is a set of vertices, then the sub-hyper graph of H induced by S is the hypergraph G with vertex set S and edge set {e [member of] E(H) | e [subset or equal to] S}.

Proposition 8 If G is a vertex-induced sub-hypergraph of H, as defined above, then C ([GIP.sub.H]) [greater than or equal to] C ([GIP.sub.G]).

Proof: Observe that [GIP.sub.G] is the restriction of [GIP.sub.H] induced by setting [x.sub.v] = 0 for all v [member of] 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.sub.1], [S.sub.2] [subset] V such that [absolute value of [S.sub.1]], [absolute value of [S.sub.2]] [greater than or equal to] c, there exists at least one edge from [S.sub.1] to [S.sub.2]. In other words, the complement of G contains no [K.sub.c,c] subgraph.

Remark. Finding the minimum number of edges in a c-interconnected graph 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.sub.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 [greater than or equal to] t! was found by Kollar, Ronyai and Szabo [10], using sophisticated methods from algebraic geometry. For the case s = t = c [greater than or equal to] 3, even the correct order of magnitude for the right answer is not known, and no explicit constructions approach the naive probabilistic bound below, which appears to be folklore.

Proposition 10 Let G be a random graph on n vertices, with each possible edge independently included with probability p > 0. Then G is (3 ln(n)/p) -interconnected with probability at least 1 - [n.sup.-31n(n)/p].

Proof: The expected number, X, of sets [S.sub.1], [S.sub.2], of size c =3 ln(n)/p with no edges between them is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

and the claimed result follows by Markov's inequality.

For explicit constructions of c-interconnected graphs, we rely on explicit constructions of expanders. The best possible expanders are Ramanujan graphs (defined below). The first explicit constructions of these were by Lubotzky, Philips and Sarnak [11] and Margulis [13].

Definition 11 Let G be a d-regular graph on n vertices. Let d = [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] xxx [greater than or equal to] [[lambda].sub.n] be the eigenvalues of G. G is called a Ramanujan graph if all eigenvalues of G are in the set {-d, d} [union] [-2 [square root of d - 1], 2[square root of 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 [square root of d - 1], 2 [square root of d - 1]].

The Expander Mixing Lemma, (see, for instance, [1, Corollary 9.2.5]) implies that connected non-bipartite Ramanujan graphs are highly interconnected. We will make use of the following corollary; a proof is included for completeness.

Lemma 12 Let G be a d-regular connected non-bipartite Ramanujan graph on n vertices. Then G is 2n/[square root of d+1]-interconnected.

Proof: Let c = 2n/[square root of d+1], and let S, T [subset] V(G) be disjoint sets of vertices such that [absolute value of S], [absolute value of T] [greater than or equal to] c. Let [x.sub.S] (resp. [x.sub.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.sub.s.sup.t][Ax.sub.T].

Let d = [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] [[lambda].sub.3] [greater than or equal to] xxx [greater than or equal to] [[lambda].sub.n] be the eigenvalues of G, and let [v.sub.1],..., [v.sub.n] be a corresponding orthonormal basis of eigenvectors. Let us express [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] in this basis. With this notation, m(S, T) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

It is easy to see that [v.sub.1] = (1,1..., 1)[square root of n], from which we observe that [[alpha].sub.1] = [absolute value of S]/[square root of n] and [[beta].sub.i] = [absolute value of T]/[square root of n]. We also note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

Substituting, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

By the Cauchy-Schwarz inequality,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

By the definition of c, this last term is non-negative. 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 c-starry if the following holds. Let [S.sub.1], [S.sub.2],..., [S.sub.m] [subset] V be pairwise disjoint sets, each of size at least c. Then there exist vertices [v.sub.1] [member of] [S.sub.1], [v.sub.2] [member of] [S.sub.2],..., [v.sub.m] [member of] [S.sub.m] that form a star in G, i.e. there is an index 1 [less than or equal to] j [less than or equal to] m such that for all i [not equal to] j, ([v.sub.j],[v.sub.i]) [member of] 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.sub.1], [S.sub.2],..., [S.sub.m] [subset] V be pairwise disjoint sets, each of size at least c.

For 1 [less than or equal to] i [less than or equal to] m, let [T.sub.i] = V \ [S.sub.i] \ [GAMMA]([S.sub.i]) = {v [member of] V [S.sub.i] | [for all]w [member of] [S.sub.i], (v, w) [??] E}. By hypothesis, [absolute value of [T.sub.i]] < c, since G contains no edge from [T.sub.i] to [S.sub.i]. Hence

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

so by the pigeonhole principle, there exists an element [v.sub.j] [member of] ([U.sub.j][S.sub.j]) \ ([U.sub.i][T.sub.i]), which is the center of the desired star.

The following corollary is incidental to our main result, but may be of independent interest.

Corollary 15 Let G = (V, E) be a c-interconnected graph. Let T be any tree on m vertices, and denote V (T) = {[t.sub.1],... ,[t.sub.m]}. Let [S.sub.1], [S.sub.2],..., [S.sub.m] [subset] V be pairwise disjoint sets such that for all i, [absolute value of [S.sub.i]] [greater than or equal to] [d.sub.i]c, where [d.sub.i] is the degree of [t.sub.i] in T. Then there exist vertices [v.sub.1] [member of] [S.sub.1], [v.sub.2] [member of] [S.sub.2],..., [v.sub.m] [member of] [S.sub.m] su ([t.sub.i],[t.sub.j]) [member of] E(T), then ([v.sub.i], [v.sub.j]) [member of] 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 ofV into k parts, there exists S [subset] V, with [absolute value of S] > 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 still has size at least n/k - ikd. Since G is c-interconnected, Lemma 14 will apply as long as n/k - ikd [greater than or equal to] c. Thus, the algorithm will run for at least (n - kc)/([k.sup.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,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

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 [OMEGA](n-kc/kd) vertices, such that [GIP.sub.G] is exactly the original GIP function of Babai, Nisan and Szegedy [3]. By Propositions 8 and 6,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

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

Theorem 19 Let G be a Ramanujan graph of degree d [approximately equal to] 16[k.sup.2]. Let H be the hypergraph of k-stars in G. Then for any partition of the inputs into k equal parts,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

But the k+1-partycommunication 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 [OMEGA](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 [OMEGA](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 w(log n) communication complexity for k = w(log n) players. Even for weaker models of communication such as the Simultaneous Messages model (cf. [12]), 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, we do not even know of 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 welcome.

received 18th February 2011, revised 20th October 2011, accepted 21st October 2011.

References

[1] N. Alon and J.H. Spencer. The probabilistic method, 2nd Ed. John Wiley & Sons, New York, 2000.

[2] L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In: Proceedings of the 27th IEEE FOCS (1986) 337-347.

[3] 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.

[4] A.K. Chandra, M.L. Furst, and R.J. Lipton. Multiparty Protocols. In: Proceedings of the 15th ACM STOC (1983) 94-99.

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

[6] P. Duris, J. Hromkovic, S. Jukna, M. Sauerhoff, and G. Schnitger. On Multi-Partition Communication Complexity. Information and Computation 194 (2004) 49-75.

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

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

[9] J. Hromkovics, J. Kari, and L. Kari. Some hierarchies for the communication complexity measures of cooperating grammar systems. Theoretical Computer Science 127 (1994), 123-147.

[10] J. Kollar, L. Ronyai, and T. Szabo. Norm-Graphs and Bipartite Turan Numbers. Combinatorica 16(1996) 399-406.

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

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

[13] G. A. Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators. Problems of Information Transmission 24 (1988), 39-46.

[14] C. H. Papadimitriou and M. Sipser. Communication Complexity. J. Computer and System Sciences 28 (1984), 260-269.

[15] T. Pitassi. Best-Partition Multiparty Communication Complexity. Course notes for Foundations of Communication Complexity, Fall 2009. Manuscript online at http://www.cs.toronto.edu/~toni/Courses/CommComplexity/Papers/ bestpartition.ps

Thomas P. Hayes ([dagger]) Department of Computer Science, University of New Mexico

([dagger]) Email: hayes@cs.unm.edu.

Printer friendly Cite/link Email Feedback | |

Author: | Hayes, Thomas P. |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Dec 1, 2011 |

Words: | 3511 |

Previous Article: | Computing tensor decompositions of finite matrix groups. |

Next Article: | The extended equivalence and equation solvability problems for groups. |

Topics: |