Communication Complexity and Quasi-randomness ^{1}

Fan R.K. Chung ^{2} and Prasad Tetali^{3}

1 Introduction

Many problems arising in interactive and distributive computation share the general framework that a number of processors wish to collaboratively evaluate a Boolean function while each processor has only partial information. The question of interest is to determine the minimum amount of information transfer required under the assumption that each processor has unlimited computational power and the messages are transferred by a “blackboard”, viewed by all processors.

One of the most interesting examples is the round-table model, proposed by Chandra, Furst and Lipton [CFL], involving k players each having a number X_{i} on his/her forehead; (so that the i-th player knows all numbers except for X_{i}). For k = 3, they proved a tight lower bound for the minimum number of bits to be exchanged to compute the sum of X_{i}’s. For general k, the lower bounds were further improved by Babai, Nisan and Szegedy [BNS] who gave a lower bound of Ω(m2^{−k}) for computing some explicit functions on k strings m-bits each.

When only two players are involved, it is just the usual model for communication complexity, which was first proposed by Yao [Y1] and has been studied extensively by many researchers [HMT, LS, MS, PS, Th]. In this paper we consider the following model generalizing both the round-table model and Yao’s model:

A number of players wish to cooperatively determine a Boolean function f(x_{1}, …, x_{k}) which accepts k inputs each m bits long. Suppose each player knows at most t inputs. The question of interest is to minimize the number of bits C_{k,t}(f) to be exchanged in order to compute f.

To determine the communication complexity C_{k,t}(f) could be a difficult problem for a general function f. The main thrust of this paper is to demonstrate the relation of communication complexity to several hypergraph properties. Consequently, lower bounds for C_{k,t} can then be established. These hypergraph properties arise in the study of random-like graph properties, so called quasi-random.

1This paper has appeared in SIAM J. Discrete Math. 6 (1993), 110-123

2Bell Communications Research, Morristown, NJ 07960.

3Visitor, DIMACS center, Rutgers University, P.O. Box 1179–Busch Campus, Piscataway, NJ 08855

Quasi-randomness was first introduced in [CGW] by showing a large number of disparate graph properties are mutually equivalent in the sense that any graph satisfying one of the properties must of necessity satisfy all of them. More recently, in [C] it was shown that several equivalence classes A_{i} form a hierarchy of classes of properties for k-uniform hypergraphs (or k-graphs, for short) and for Boolean functions with k input arguments (also called k-functions). The quasi-random class A_{k}, introduced in [CG1], consists of graph properties such as : “For any fixed s ≥ 2k all k-graphs on s vertices appear almost equally often as induced subgraph of G.” On the other hand, in A_{0} there is the property that the number of edges in G is approximately the same as the number of non-edges in G. The detailed description of the equivalence classes A_{i} and the hierarchy

A_{0} ⊃ A_{1} ⊃ ⋯ ⊃ A_{k}

will be described in Section 2.

Among various properties in the equivalence class A_{i}, there are two interesting invariants– the i-discrepancy and the i-deviation (see Section 2 for definition). Intuitively, the i-deviation provides a quantitative indication as to how much the graph deviates from random graphs. Discrepancy is useful in various contexts, in particular, corresponding to various statistical tests arising in complexity analysis. Roughly speaking, discrepancy is a “global” property that is often hard to compute, while deviation is a “local” property that is easy to compute. The quasi-randomness results imply that the i-discrepancy of a function is small if and only if its i-deviation is small. Furthermore, the i-discrepancy can be used to characterize the communication complexity C_{k,i}. Using the results of [BNS], this further leads to explicit construction of functions f_{k,t} with communication complexity C_{k,t} lower bounded by Ω(mc^{−t}). One of the consequences is a simple proof of the lower bound of Ω(m2^{−k}) on the communication complexity of the “generalized inner product” function as described in Section 3.

The communication complexity C_{k,t} corresponds in a natural way to the complexity of a t-head Turing machine that computes Boolean functions with k inputs (as discussed in Section 3). As an immediate consequence, lower bounds for time-space tradeoffs can be obtained. We prove that for any fixed t, any (t − 1)-head TM computing the function f_{k,t} on m-bit strings requires a time-space tradeoff of T S ≥ Ω(m^{2}).

Discrepancy can also be interpreted in terms of a game of switches and lights (also discussed in Section 3). Apart from being interesting in its own right, this interpretation yields an short proof that the communication complexity C_{k,i} of a random k-function f is at least \frac{(k−i+1)}{2}m.

In Section 4, we conclude with some open problems and remarks about the relations of communication complexity to other complexity issues. The quantitative quasi-random classes for k-graphs with edge density α and various expansion properties are also mentioned.

2 Quasi-random Classes

2.1 notation

We use \binom{X}{k} to denote the set of k-element subsets of a set X of cardinality ≥ k. A k-graph G = (V, E) consists of a set V = V (G), called the vertices of G, and a subset E = E(G) of the set \binom{V}{k} called the edges of G. Throughout this paper, G denotes a k-graph on n vertices unless otherwise specified.

For X ⊆ V, G[X] denotes the subgraph of G induced by X, i.e. G[X] = (X, E ∩ \binom{X}{k}). Let H denote an l-graph where l < k and V (H) = V (G). The set E(G, H) of edges of G induced by H is defined to be:

E(G, H) = \{x ∈ E(G) : \binom{x}{l} ⊆ E(H)\}

For l = 1, the edge set of H is just a subset of V (G) and E(G, H) = E(G[H]). We denote e(G) =| E(G) | and e(G, H) =| E(G, H) |.

Discrepancy. For i ≥ 2, the i − discrepancy of G, denoted by disc_{i}(G), is defined as follows:

disc_{i}(G) = max_{H:(i−1)−graph} \frac{| e(G, H) − e(Ḡ, H) |}{| V (G) |^{k}}

where Ḡ denotes the complement of G with edge set \{x ∈ \binom{V}{k} : x ∉ E(G)\}. We remark that disc_{2} is often called discrepancy in the literature (see [ES]). disc_{i} can be viewed as a natural generalization of discrepancy.

We let μ_{G} : \binom{V}{k} → \{−1, 1\} denote the edge function of G, i.e. for x ∈ \binom{V}{k},

μ_{G}(x) = \{ \begin{matrix}−1 & if x ∈ E \\ 1 & otherwise \end{matrix}

Let V^{k} denote the set of k-tuples (v_{1}, …, v_{k}), v_{i} ∈ V, where the v’s are not necessarily distinct. Let ∏_{G}^{(i)} : V^{k+i} → {−1, 1} denote the following function of G.

∏_{G}^{(i)}(u_{1}, …, u_{2i}, v_{i+1}, …, v_{k}) = ∏_{ϵ_{1}} ⋯ ∏_{ϵ_{i}} μ_{G}(ϵ_{1}, …, ϵ_{i}, v_{i+1}, …, v_{k})

where ϵ_{j} ∈ {u_{2j−1}, u_{2j}} for j ≤ i. Note that ∏_{G}^{(i)} is a product of 2^{i} terms each of which is an edge function. For i = 0, we define ∏_{G}^{0} = μ_{G}.

Deviation. The i − deviation of G, denoted by dev_{i}(G), is defined as follows:

dev_{i}(G) = \frac{1}{n^{k+i}} ∑_{u_{1},...u_{k+i}} ∏_{G}^{(i)}(u_{1}, …, u_{k+i})

Thus dev_{i}(G) assumes a value between -1 and 1. (Another interpretation is that n^{k+i} dev_{i} is the difference of the number of “even partial (squashed) octahedrons” and the “odd partial (squashed) octahedrons” as described in [CG1] and [CG2].)

2.2 quasi-randomness

We will use the following convention. Suppose we have two classes P = P (o(1)) and P′ = P′(o(1)), each with occurrences of the asymptotic o(1) notation. By the implication “P ⇒ P′”, we mean that for each ϵ > 0 there is a δ > 0 (a function of ϵ and k but independent of n) such that if G(n) satisfies P (δ) then it also satisfies P′(ϵ), provided n > n_{0}(ϵ). Two properties P and P′ are said to be equivalent if P ⇒ P′ and P′ ⇒ P.

Here we define several classes of properties for k-graphs.

For i = 0 and 1, define the properties

R_{0} : e(G) − e(Ḡ) = o(n^{k}) where Ḡ denotes the complement of G.
R_{1} : G is almost regular. That is,

∑_{u_{1},...,u_{k−1}} (d^{+}(u_{1}, …, u_{k−1}) − d^{−}(u_{1}, …, u_{k−1}))^{2} = o(n^{k+1})

where d^{+}(u_{1}, …, u_{k−1}) =| {v ∈ V : {u_{1}, …, u_{k−1}, v} ∈ E(G)} |, and d^{−}(u_{1}, …, u_{k−1}) =| {v ∈ V : {u_{1}, …, u_{k−1}, v} ∉ E(G)} |. For i ≥ 2, define

R_{i} : For every (i − 1)-graph H , e(G, H) − e(Ḡ, H) = o(n^{k})

In [CG1] it was shown that the property dev_{k}(G) = o(1) for a hypergraph G is equivalent to a number of properties, among which are :

Q : For all k-graphs G′ on 2k vertices, the number of (labelled) occurences
of G′ in G as an induced subgraph is (1 + o(1))n^{2k}2^{−\binom{2k}{k}}.

Let s denote a fixed integer and s ≥ 2k.

Q(s) : For all k-graphs G′(s) on s vertices the number of (labelled) occurrences
of G′ in G as an induced subgraph is (1 + o(1))n^{s}2^{−\binom{s}{k}}.

In [C] the deviation property is further generalized to the following property (denoted P_{i}) For i ≥ 0,

P_{i} : dev_{i}(G) = o(1).

The main results of [C] can be summarized in the following two theorems.

Theorem 1 Properties P_{i} and R_{i} are equivalent for i = 0, …, k. In particular for i ≥ 2, we have

(i) disc_{i}(G) = max_{H:(i−1)−graph} \frac{| e(G, H) − e(Ḡ, H) |}{| V (G) |^{k}} < (dev_{i}(G))^{1/2^{i}}
(ii) dev_{i}(G) < 4^{i} (disc_{i}(G))^{1/2^{i}}

Theorem 1, in fact, has interesting computational implications. It is easy to see that computing disc_{i} for general G (naively) takes time O(2^{n^{i}}.n^{k}), since the number of i-graphs is O(2^{n^{i}}) and for each i-graph H, computing | e(G, H) − e(Ḡ, H) | takes O(n^{k}) time. On the other hand, dev_{i} can be computed in time O(n^{k+i}) since dev_{i} is a sum of n_{k+i} terms, each term in turn is a product of 2^{i} subterms each of which is an edge function. Thus Theorem 1 leads to the following conclusion: Although it takes exponential time to compute disc_{i} exactly, an approximation can be obtained by using dev_{i} in only polynomial-time. We remark that it would be of interest if the power 1/2^{i} on the right-hand sides of the inequalities could be improved.

Theorem 2 Let A_{i} denote the equivalence class of k-graphs for which P_{i} holds. Then,

A_{0} ⊃ A_{1} ⊃ A_{2} ⋯ ⊃ A_{k}

The family A_{i} = A_{i}^{(k)} of k-graphs is said to be (k, i)-quasi-random, or sometimes i-quasi-random if there is no confusion. The term, “k-quasi-random” for k-graphs is the same as “quasi-random” as in previous papers.

Here we describe the constructions of k-graphs G_{i}, separating class A_{i} from A_{i+1}, for it is used in a later section on lower bounds for communication complexity. Since P_{i} ⇒ P_{i+1} for any i, we have A_{i} ⊇ A_{i+1}. To show A_{i} ⊃ A_{i+1}, for i = 0, …, k − 1, the idea is to construct k-graphs G_{i} with the property that G_{i} ∈ A_{i} and G_{i} ∉ A_{i+1} using quasi-random graphs as the basic building blocks. In [CG1], two families of quasi-random k-graphs are given, one of which is the Paley k-graph P_{k} with V (P_{k}) = {1, 2, …, n} (n is a prime) and μ_{P_{k}}(u_{1}, …, u_{k}) = 1 if and only if u_{1} + ⋯ + u_{k} is a quadratic residue modulo n.

For each i, we define the k-graph G_{i} as follows:

V (G_{i}) = V (P_{i}) = V
E(G_{i}) = \{x ∈ \binom{V}{k} :| \binom{x}{i} ∩ E(P_{i}) |≡ 0 (mod 2)\}

Claim G_{i} ∈ A_{i} \ A_{i+1} Proof: Part 1 G_{i} ∈ A_{i} : It is shown in [C] (by making use of the character sum inequality of Burgess [B]) that

dev_{i}(G_{i}) = O(n^{−1/2})

Therefore G_{i} satisfies Property P_{i} and hence is in A_{i}. Part 2 G_{i} ∉ A_{i+1}: Consider the set E(G_{i}, P_{i}) of edges of G_{i} induced by the Paley graph P_{i}. An edge x is in E(G_{i}, P_{i}) means every i-subset of x has a sum which is a quadratic nonresidue. By definition, x contains an even number of i-sets each of which has a sum which is quadratic nonresidue. This can happen only when \binom{k}{i} ≡ 0 (mod 2). Therefore either E(G_{i}, P_{i}) is empty or E(Ḡ_{i}, P_{i}) is empty. Since k and i are all fixed integers,

| E(G_{i}, P_{i}) − E(Ḡ_{i}, P_{i}) | = | E (\binom{V}{k}, P_{i}) |
= (1 + o(1)) \frac{n^{k}}{2^{\binom{k}{i}}}
≠ o(n^{k})

Thus G_{i} ∉ A_{i+1}.

We now describe a more general construction of k-functions G_{i} using any quasi-random graph in A_{k} as the basic building block. General construction for G_{i} ∈ A_{i} \ A_{i+1}. Note that the proof of Part 2 is quite general– does not make use of the fact that the basic building block was the Paley k-graph P_{k}. We show here that, in fact, any quasi-random graph in A_{k} serves the purpose as well. (For example, the family of “even intersection” k-graphs defined in [CG1] is an equally good choice.) First we need the following definition of the “neighborhood graph” of a k-graph. Given a k-graph G, the neighborhood graph G(v) of a vertex v is the graph having vertex set G \ {v} and edge set E(G(v)) = \{x ∈ \binom{V}{k−1} : x ∪ \{v\} ∈ E(G)\}.

Let H_{i} be a quasi-random i-graph on n vertices. Then we define the k-graph G_{i} as follows:

V (G_{i}) = V (H_{i}) = V
E(G_{i}) = \{x ∈ \binom{V}{k} :| \binom{x}{i} ∩ E(H_{i}) |≡ 0 (mod 2)\}

We outline the proof of G_{k−1} ∈ A_{k−1} \ A_{k}. Part 1 G_{k−1} ∈ A_{k−1} : As a direct consequence of the definition of a neighborhood graph, we have

dev_{i}(G) = \frac{1}{n} ∑_{v∈V} dev_{i}(G(v))

For a fixed vertex v, consider the neighborhood graph G_{k−1}(v) of the k-graph G_{k−1}. The edge set of G_{k−1}(v) can be characterized as follows.

E (G_{k−1}(v)) = E_{1} ∪ E_{2}

where

E_{1} = \{y ∈ \binom{V}{k−1} : y ∈ H_{k−1} and E(H_{k−1}(v)) ∩ \binom{y}{k−2} ≡ 0 (mod 2)\} and
E_{2} = \{y ∈ \binom{V}{k−1} : y ∉ H_{k−1} and E(H_{k−1}(v)) ∩ \binom{y}{k−2} ≡ 1 (mod 2)\}

Thus

μ_{G_{k−1}(v)} = μ_{H_{k−1}}.μ_{δ(H_{k−1}(v))} (∗)

where δ(H_{k−1}(v)) is defined to be :

δ(H_{k−1}(v)) = \{y ∈ \binom{V}{k − 1} : E(H_{k−1}(v)) ∩ \binom{y}{k − 2} ≡ 0 (mod 2)\}

It is not very hard to verify that (∗) implies that

dev_{k−1}(G_{k−1}(v)) = dev_{k−1} (H_{k−1})

Thus

dev_{k−1}(G_{k−1}) = ∑_{v} \frac{dev_{k−1} (G_{k−1}(v))}{n} = o(1), since H_{k−1} ∈ A_{k−1}

This shows G_{k−1} ∈ A_{k−1}. Part 2 The proof of G_{k−1} ∉ A_{k} is identical to the proof of Part 2 with the Paley graph construction.

3 Communication Complexity

3.1 Quasi-random classes of functions

A k-function is a function f from V^{k} to {−1, 1}. We note that k-functions can be viewed as ordered k-graphs and k-graphs can be regarded as symmetric k-functions. In fact, most known lower bound constructions for k-functions are symmetric and thus can be reduced to hypergraphs. We shall see in the following that the notions of discrepancy and deviation extend to k-functions as well. For convenience, we use the same notation (disc and dev) for discrepancy and deviation of k-functions, and we warn the reader to interpret appropriately depending on the context. Thus, for example, disc(f) refers to the deviation of a k-function f, whereas disc(G) stands for that of a k-graph G.

Let I denote a subset of size i of {1, …, k} = [k]. For a k-tuple x = (x_{1}, …, x_{k}), we define x_{I} to be an i-tuple (x_{a_{1}}, …, x_{a_{i}}) where a_{1} < … < a_{i} and a_{i} ∈ I. Discrepancy. Let H_{i} denote a family of i-functions where i < k and the members of H_{i} are indexed by \binom{[k]}{i}, denoted by h_{I}. We define E(f, H_{i}) as follows:

E(f, H_{i}) = {x ∈ V^{k} : f(x) = −1 and for every h_{I} ∈ H_{i}, h_{I}(x_{I}) = −1} .

We denote the cardinality of E(f, H_{i}) by e(f, H_{i}). The i-discrepancy of f is defined as follows

disc_{i}(f) = max_{H_{i−1}} \frac{| e(f, H_{i−1}) − e(−f, H_{i−1}) |}{| V |^{k}}

Deviation. Define ∏_{f,I}^{(i)} : V^{k+i} → {−1, 1} by

∏_{f,I}^{(i)}(x_{1}, …, x_{k+i}) = ∏_{ϵ_{1}} ⋯ ∏_{ϵ_{k}} f(ϵ_{1}, …, ϵ_{k})

where ϵ_{j} ∈ {x_{j+m−1}, x_{j+m}} if j ∈ I and m =| I ∩ [1, j] |; and ϵ_{j} = x_{i+m} if j ∉ I. The i-deviation of f is defined to be:

dev_{i}(f) = max_{I} \frac{1}{n^{k+i}} ∑_{x_{1},...,x_{k+i}} ∏_{f,I}^{(i)}(x_{1}, …, x_{k+i})

where I ranges over all subsets of [k] of size i. For fixed i, we consider the following properties for a k-function:

R̃_{i} : For i ≥ 2, for every family H_{i−1} of i − 1-functions
e(f, H_{i−1}) − e(−f, H_{i−1}) = o(n^{k})
P̃_{i} : dev_{i}(f) = o(1).

It can be shown that the properties R̃_{i} and P̃_{i} are equivalent. In fact, the analogs of Theorems 1 and 2 for k-functions also hold (see [C]).

3.2 Multiparty communication games

In ([BNS]), Babai, Nisan and Szegedy considered the communication complexity for k-functions where each of the k players knows exactly k − 1 inputs. Let x = (x_{1}, …, x_{k}) denote an input chosen uniformly over all k-tuples. Then the communication complexity is bounded by log \frac{1}{Γ(f)} where

Γ(f) = max_{S} (Pr[x ∈ S and f(x) = −1] − Pr[x ∈ S and f(x) = 1])

where S ranges over so-called “cylinder intersections”. The theorem below generalizes the result of [BNS].

We first extend the notion of “cylinders” and “cylinder intersections” for functions in class A_{i}. A subset of S^{(i−1)} of k-tuples is called a cylinder if membership in S^{(i−1)} depends only on i − 1 coordinates. Thus, based on which i − 1 of the coordinates the k-tuple depends on, there will be \binom{k}{i−1} types of S^{(i−1)} in A_{i}. Furthermore, a subset of k-tuples is a cylinder intersection if it can be represented as an intersection of cylinders. Let ∩S^{(i−1)} represent a subset which is an intersection of all \binom{k}{i−1} types of cylinders. We define Γ_{i}(f) of f to be

Γ_{i}(f) = max_{∩S^{(i−1)}} (Pr[x ∈ ∩S^{(i−1)} and f(x) = −1] − Pr[x ∈ ∩S^{(i−1)} and f(x) = 1])

Let I denote the subset of i coordinates that S^{(i)} depends on. Then we have the following natural correspondence between cylinders S^{(i)} and i-functions h_{I}, for i = 1, …, k − 1:

x ∈ S^{(i)} ⇔ h_{I}(x_{I}) = −1

and

x ∈ ∩S^{(i)} ⇔ for every h_{I} ∈ H_{i}, h_{I}(x_{I}) = −1.

This enables us to prove the following. Theorem 3 For i = 2, …, k,

Γ_{i}(f) = disc_{i}(f)
C_{i}(f) ≥ log \frac{1}{disc_{i}(f)}

where C_{i}(f) denotes the communication complexity of f in class A_{i} Proof. Since x is chosen uniformly over all 2^{mk} possible k-tuples, we have

Γ_{i}(f) = max_{∩S^{(i−1)}} (Pr[x ∈ ∩S^{(i−1)} and f(x) = −1] − Pr[x ∈ ∩S^{(i−1)} and f(x) = 1])
= max_{∩S^{(i−1)}} \frac{1}{2^{mk}} [| \{x : x ∈ ∩S^{(i−1)} and f(x) = −1\} | − | \{x : x ∈ ∩S^{(i−1)} and f(x) = 1\} |]
= max_{H_{i−1}} \frac{1}{n^{k}} [e(f, H_{i−1}) − e(−f, H_{i−1})]
= disc_{i}(f)

The second part of the proof is similar to that of Lemma 2.2 in [BNS]; we include it here for the sake of completeness. Let P be any valid protocol for the given function f. We denote by P (x), the value of f(x) as computed by the protocol P. Let N be the number of different possible strings that may be written on the board by P. We want to prove that N ≥ 1/Γ_{i}(f). With each string s we associate X_{P,s}, the set of inputs for which s gets written on the board by P . It is not hard to see that X_{P,s} is a cylinder intersection ∩S^{(i−1)}.

Let x be chosen uniformly over all k-tuples. Since P is a valid protocol,

| Pr[P (x) = f(x)] − Pr[P (x) ≠ f(x)]| = 1

We can estimate the same by summing over different X_{P,s}:

| Pr[P (x) = f(x)] − Pr[P (x) ≠ f(x)]|

≤ ∑_{s} | Pr [P (x) = f(x) and x ∈ X_{P,s}] − Pr [P (x) ≠ f(x) and x ∈ X_{P,s}]

where s ranges over all possible strings that may be written.

Thus

1 ≤ ∑_{s} | Pr [P (x) = f(x) and x ∈ X_{P,s}] − Pr [P (x) ≠ f(x) and x ∈ X_{P,s}]
= ∑_{s} Pr [f(x) = 1 and x ∈ X_{P,s}] − Pr [f(x) = −1 and x ∈ X_{P,s}]
≤ ∑_{s} Γ_{i}(f), since X_{P,s} is a cylinder intersection
= NΓ_{i}(f)

This proves

C_{i}(f) = log N ≥ log [\frac{1}{Γ_{i}(f)}] .

□

We remark that we do not restrict the number of players. Suppose we consider the minimum number C_{k,i}(p) of bits required to be exchanged for some p players, each knowing at most i − 1 inputs of a k-function. It is easy to see that C_{k,i}(p) = C_{k,i}(p′) if p′ > p. Moreover, C_{k,i}(p′′) > C_{k,i}(p) if p′′ < p.

Fact. For any k-function f, C_{i}(f) ≤ (k − i + 1)m. Proof. If (k − i + 1) inputs get written on the board, then some player would know all k inputs. This could be done, trivially, if a player always writes an input that is not already present on the board.

Theorem 4 For a random k-function f, C_{i}(f) ≥ \frac{(k−i+1)}{2}m.

Proof. For a random k-function f, it is not hard to verify that with probability approaching 1, we have |e(f, H) − e(−f, H)| = O(n^{(k+i−1)/2}) for every (i − 1)-function H and this is best possible. Using similar methods as in [ESp], this implies,

disc_{i}(f) = max_{H_{i−1}} \frac{|e(f, H_{i−1}) − e(−f, H_{i−1})|}{n^{k}}
= O(n^{(−k+i−1)/2})
= O(2^{(−k+i−1)m/2})

Hence

C_{i}(f) = Ω (\frac{(k − i + 1)}{2}m) .

In [BNS] examples of functions f with C_{k}(f) = Ω (\frac{m}{2^{k}} ) are given. Here we give a short proof for the following “Box-product” of functions.

Box-product of k-functions and Deviation. Let f : V^{k} → {−1, 1} and g : W^{k} → {−1, 1} be two k-functions. We define f□g : (V × W)^{k} → {−1, 1} to be the following k-function

f□g ((x_{1}, y_{1}), …, (x_{k}, y_{k})) = f(x_{1}, …, x_{k}).g(y_{1}, …, y_{k})

It can be shown that (also see [CG2])

dev_{i}(f□g) = dev_{i}(f).dev_{i}(g)

Example 1. Consider the graph G on three vertices v_{1}, v_{2}, v_{3}, with the edges {v_{1}, v_{2}} and {v_{2}, v_{3}}; let V = {v_{1}, v_{2}, v_{3}} and f denote the edge function of G. It is easy to check that dev_{0}(f) = dev_{1}(f) = 1/9. Taking the Box-product of f with itself gives us the function f′ = f□f with the properties: dev_{0}(f′) = dev_{1}(f′) = 1/81. Example 2. Consider the following “generalized inner product function” f_{m}, defined on subsets S_{i} of a set of size m.

f_{m}(S_{1}, …, S_{k}) = \{ \begin{matrix}1 & if S_{1} ∩ … ∩ S_{k} is even \\ −1 & otherwise \end{matrix}

For the special case m = 1, f_{1}, each S_{i} is a singleton or empty. It is easy to verify, by induction on m, that

f_{m} = f_{1}□ ⋯ □f_{1} (m times)

Since dev_{i}(f_{1}) = 1 − 2^{−k−i+1} = c < 1, we readily obtain dev_{i}(f_{m}) < c^{m}. In particular, dev_{k}(f_{m}) < c^{m}, where c < 1. This implies that disc_{k}(f_{m}) < c^{m/2^{k}}. And by Theorem 3,

C_{k}(f_{m}) ≥ log \frac{1}{disc_{k}(f_{m})} = Ω (\frac{m}{2^{k}} )

Therefore, we prove the following.

Theorem 5 The generalized inner product function f_{m} has C_{k}(f_{m}) = Ω (\frac{m}{2^{k}} ).

One of the main results in [BNS] is to establish an upper bound for disc_{k}f_{m} and thereby obtain a lower bound for C_{k}(f_{m}). Independently, an upper bound for disc_{k}f_{m} is also proved in [CG1]. However, both the proofs are more complicated in comparison to the one we described above. The significance of the Box-product is thus apparent. Starting with a function with dev_{i} < 1, we can construct functions with exponentially small dev_{i} by repeatedly considering Box-product of the original function with itself.

The following result shows that Theorem 5 is an instance in a more general setting.

Theorem 6 There are explicit k-functions f satisfying

C_{i}(f) = Ω (\frac{m}{2^{i}}) .

Proof. Recall from Section 2.2, we constructed k-graphs G_{i} ∈ A_{i} \ A_{i+1} for which

dev_{i}(G_{i}) = O(n^{−1})

In terms of k-functions, this implies that

dev_{i}(f_{k,i}) = O(2^{−m})

So

disc_{i}(f_{k,i}) ≤ (dev_{i})^{1/2^{i}}
= O(2^{−m/2^{i}})

This implies C_{i}(f_{k,i}) = Ω (\frac{m}{2^{i}}) .

Remark. One of the important questions is to find communication complexity lower bounds that do not decrease exponentially in k for some explicit k-function. This would improve results [BNS] on pseudorandom sequences, time-space tradeoffs for multi-head Turing machines, and length-width tradeoffs for oblivious branching programs. Improving the relation (Theorem 1) between disc_{i} and dev_{i} would be significant for the same reason.

3.3 Application to Turing machines

Let f be a k-function. Under our general communication model, we have the following analog of the result of Babai et al [BNS] for the time-space tradeoff of Turing machines and we omit the proofs here.

Lemma 1 Any i-head Turing machine that computes a k-function f from the following input:

< x_{1} > ∗ ∗ ∗∗ < x_{2} > ∗ ∗ ∗ ∗ ⋯ ∗ ∗ ∗ ∗ < x_{k} >

(where ∗ ∗ ∗∗ means l spaces on the input tape) requires a time-space tradeoff of T S ≥ lC_{i+1}(f)/i.

And hence

Theorem 7 For any fixed i, any i-head Turing machine computing the k-function f_{k,i} requires a time-space tradeoff of T S ≥ Ω(m^{2}).

3.4 Discrepancy and the switching lights model

There is yet another interpretation for disc_{i} in terms of the switching lights model, first described in [Sp] for the two dimensional case. The game consists of an n × n array A of lights and 2n switches, one for each row x_{i} and column y_{j}. Each switch when thrown changes each light in its line from off to on or from on to off. The difference is defined as the absolute value of the number of lights on minus the number of lights off ranging over all possible settings of the switches. Given an initial configuration, the object is to maximize the difference. Mathematical formulation of this problem shows that maximizing this difference corresponds to computing the discrepancy (the Γ function) in the multiparty communication model in a sense made precise in the theorem below.

Consider a k-dimensional array of n^{k} lights. Imagine each switch controlling an i-dimensional hyperplane of n^{i} lights; i.e. each switch when thrown changes each light in the particular hyperplane from off to on or from on to off. There are (i + 1)n^{k−i} such switches and the aim is to maximize the difference between the number of lights on and off. We denote this by D_{k}^{i}.

Thus, in k-dimensions, we formulate k − 1 discrepancy problems associated with the switching game.

In 3-dimensions we have two problems: D_{3}^{2} and D_{3}^{1}. The distinction is that each switch controls a plane of lights in one case and a line of lights in the other. Intuitively, we would expect D_{3}^{1} to be higher than D_{3}^{2}, and the intuition is right. The mathematical formulation of this case (D_{3}^{2}) is as follows.

Let the array of n^{3} lights be represented by A(ijk) = ±1, for i, j, k = 1, …, n. Thus 1 represents a light on and −1 a light off. Further we let x_{i}, y_{j}, z_{k} represent the 3n switches. “Throwing” a switch x_{i} corresponds to setting x_{i} = −1. Given an initial setting of A(i, j, k) = ±1 we define the discrepancy of A to be

D(A) = max_{x_{i},y_{j},z_{k}=±1} A(i, j, k) · x_{i}y_{j}z_{k}

i.e. the maximum difference between the number of lights on and off that one can obtain by throwing the switches. Further we define

D_{3}^{2} = min_{A} max_{x_{i}y_{j}z_{k}} A(i, j, k)x_{i}y_{j}z_{k}

to be the maximum ranging over all possible initial configurations of A. The case D_{k}^{i} for general i have a similar mathematical formulation.

The following theorem establishes the equivalence between D_{k}^{i} and the “discrepancy” Γ_{i} in the context of multiparty communication complexity. Firstly, we associate with a given k–input function f, the k–dimensional array A_{f} of size 2^{m} × ⋯ × 2^{m} where

A_{f}(i_{1}, …, i_{k}) = f(x_{1} = i_{1}, …, x_{k} = i_{k})

Thus we are assuming (without loss of generality) that each input x_{j} ranges from 1 to 2^{m}. We then have the following: Theorem 8

Γ_{i}(f(m)) = \frac{1}{2^{mk}} D_{k}^{k−i}(A_{f})

Proof. Basically, the number of inputs each player knows corresponds to the number of coordinates required to specify a switch, and the possible bit sequences by the players correspond to the switch settings. We describe the proof for i = k − 1. The general case is quite similar and will be omitted. It is not difficult to see that Γ_{k−1} can be rewritten as follows (see [BNS]).

Γ_{k−1}(f(m)) = max_{ϕ_{1},...,ϕ_{k}} |E [f(x_{1}, …, x_{k})ϕ_{1}(x_{1}, …, x_{k}) ⋯ ϕ_{k}(x_{1}, …, x_{k})] |

where the expectation is over all possible 2^{mk} choices of x_{1}, …, x_{k}, and the maximum is taken over all functions ϕ_{j} : ({0, 1}^{m})^{k} → {0, 1} such that ϕ_{j} does not depend on x_{j}. (Intuitively, ϕ_{j} corresponds to possible messages communicated by player P_{i}.) Thus

Γ_{k−1}(f(m)) = \frac{1}{2^{mk}} max_{ϕ_{1},...,ϕ_{k}} | ∑_{x_{1}} ⋯ ∑_{x_{k}} [f(x_{1}, …, x_{k})ϕ_{1}(x_{1}, …, x_{k}) ⋯ ϕ_{k}(x_{1}, …, x_{k})] |

Whereas discrepancy of A_{f} in the switching game is defined as

D_{k}^{1}(A_{f}) = max_{s_{i_{1}},...,s_{i_{k}}} ∑_{i_{1}=1}^{2^{m}} ⋯ ∑_{i_{k}=1}^{2^{m}} A(i_{1}, …, i_{k})s_{i_{1}} ⋯ s_{i_{k}}

where the switch s_{i_{j}} : {1, …, 2^{m}}^{k} → {0, 1} depends on all but index i_{j}. It is now easy to see that the functions ϕ_{j} correspond to the switches s_{i_{j}}.

Thus Γ_{k−1}(f(m)) = \frac{1}{2^{mk}} D_{k}^{1}(A_{f}) □

The following theorem appears in [ESp] in the form of a result on a hypergraph-coloring problem.

Theorem 9 There exist arrays A of n^{k} lights such that

D_{k}^{i}(A) ≤ c(k, i)n^{(k+i−1)/2}

where c(k, i) is an explicit constant depending on k and i.

Proof. The proof is straight forward using the probabilistic method, and can be found in [T].

Remark 1. Theorem 7 shows that for a random k-function f, disc_{i}(f) = O (n^{(k+i−1)/2}). Thus this yields a simple proof of

C_{i}(f) ≥ log (n^{(k+i−1)/2})
= log (2^{(k+i−1)m/2})
= \frac{(k + i − 1)}{2}m.

Remark 2. Note that Theorem 9 guarantees the existence of an array A such that D_{k}^{i}(A) ≤ cn^{(2k−i)/2}. Can we, in fact, construct such an array? The question is open for k > 2. For k = 2 it is known that an n × n Hadamard matrix H works! That is,

D_{2}^{1}(H) ≤ n^{3/2}

However, it is not clear how to generalize the notion of Hadamard matrices for the case of k > 2. Apart from being an interesting derandomization question by itself, this has the following implications. In view of Theorem 8, upper bounds on D_{k}^{i} yield, in turn, upper bounds on Γ_{i}, and further give lower bounds on the communication complexity of multiparty protocols. Thus, making Theorem 5.1 constructive seems to be an interesting open problem.

Remark 3. The inequality in Theorem 7 is the best possible. That is, given any arbitrary initial configuration for the array of lights, one can set the switches such that the maximum difference is Ω(n^{(k+i−1)/2}). In fact, the random configuration achieves the bound which can be proved by generalizing the result in [ESp]. In fact, the method of conditional expectations can be used in derandomizing the algorithm and a sequential as well as a parallel algorithm is described in [T] to achieve the optimal setting of the switches.

4 Problems and Remarks

In addition to various problems that were mentioned in previous sections, many problems and directions remain to be explored. It would be of interest to establish relations and connections with other complexity problems. For example, an interesting relation between circuit complexity and quasi-randomness has been demonstrated through some recent work of Hastad and Goldmann [HG]. Using the results of [BNS], Hastad and Goldmann show that (inter alia), evaluating the generalized inner product function on k + 1 inputs by a depth 3 unweighted threshold circuit with bottom fanin at most k would require size 2^{Ω(n/k4^{k})}. One way to improve these lower bounds is to come up with explicit hypergraphs or k-functions with smaller discrepancy or higher communication complexity.

Although we deal with hypergraphs with the edge density 1/2, the results can easily be generalized to hypergraphs or functions with any fixed edge density α, for 0 < α < 1. For a function f from V^{k} to {−1, 1}, we define f_{α}(x) = 1 − α if f(x) = −1 and f_{α}(x) = −α if f(x) = 1. In [C], dev_{i}f_{α}, disc_{i}f_{α} and the class A_{i,α} are defined analogous to dev_{i}, disc_{i}, and A_{i}. In particular, the 2-discrepancy disc_{2,α} is described as follows:

disc_{2,α}(f) = max_{X⊆V} \frac{e(f, X) − α | X |^{k}}{| X |^{k}}

where e(f, X) =| \{x ∈ \binom{X}{k} : f(x) = −1\} |. Suppose we choose α to be e(f, X) =| \{x ∈ \binom{V}{k} : f(x) = −1\} | / | V |^{k} (which can be viewed as the density of “ordered” hyper-edges). Then disc_{2,α}(f) associates with the maximum quantity that the number of ordered-edges in a subset X can differ from the average. If we can use dev_{2,α} to (upper) bound disc_{2,α}(f), then we can (lower) bound the number of edges leaving X from every X ⊆ V and thus assert the expanding property of the hypergraphs.

References

[B] D.A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. 12 (1962), 179-192.

[BFL] L. Babai, P. Frankl and J. Simon, Complexity classes in communication complexity theory, 27th FOCS (1986), 337-347.

[BNS] L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols and logspace-hard pseudorandom sequences, 21st STOC (1989), 1-11.

[C] F.R.K. Chung, Quasi-random classes of hypergraphs, Random Structures and Algorithms, 1 (1990), 363-382.

[C2] F.R.K. Chung, Regularity lemmas for hypergraphs and quasi-randomness, Random Structures and Algorithms, 2 (1991), 241-252.

[CFL] A.K. Chandra, M.L. Furst and R.J. Lipton, Multiparty protocols, 24th FOCS (1983), 94-99.

[CGW] F.R.K. Chung, R.L. Graham and R.M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345-362.

[CG1] F.R.K. Chung and R.L. Graham, Quasi-random hypergraphs, Random Structures and Algorithms, 1 (1990), 105-124.

[CG2] F.R.K. Chung and R.L. Graham, Quasi-random set systems, J. of AMS, 4 (1991) 151-196.

[ES] P. Erdős and V.T. Sós, On Ramsey-Turán type theorems for hypergraphs, Combinatorica 2 (1982), 289-295.

[ESp] P. Erdős and J. Spencer, Imbalances in k-colorations, Networks 1 (1971), 379-385.

[HG] J. Hastad and M. Goldmann, On the Power of Small-Depth Threshold Circuits, 31st FOCS (1990), 610-618.

[HMT] A. Hajnal, W. Maass, and G. Turán, On the Communication Complexity of graph properties, 20th STOC (1988), 186-191.

[MS] K.Melhorn and E.M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing, 14th STOC (1982), 330-337.

[L] L. Lovász, Computational Complexity : A Survey, in Paths, Flows, and VLSI-Layout, (B. Korte et al eds.), Springer-Verlag (1990), 235-266.

[LS] L. Lovász and M. Saks, Lattices, Möbius functions and communication complexity, 29th FOCS (1988), 81-90.

[PS] C.H. Papadimitriou and M. Sipser, Communication Complexity, 14th STOC (1983) 196-200.

[T] P. Tetali, Analysis and Applications of Probabilistic Techniques, Ph.D. Thesis, New York University (October 1991).

[SS] M. Simonovits and V.T. Sós, Szemerédi-partition and Quasi-randomness, Random Structures and Algorithms 2 (1991), 1-10.

[Sp] J. Spencer, Ten Lectures on the Probabilistic method, SIAM Publications, Philadelphia (1987).

[Sz] E. Szemerédi, Regular partitions of graphs, Problémes combinatoires et théorie des graphs, Coll. CNRS (1976), 399-401.

[Th] C.D. Thompson, Area-time complexity for VLSI, 11th STOC (1979), 81-88.

[Y1] A.C.C. Yao, “Some complexity questions related to distributive computing”, 11th STOC (1979), 209-213.