The Cost of the Missing Bit: Communication Complexity with Help

László Babai^{∗}  Thomas P. ; Hayes^{†}  Peter G. ; Kimmel^{‡}

November 6, 2000

Dedicated to the Memory of Paul Erdős

Abstract

We generalize the multiparty communication model of Chandra, Furst, and Lipton (1983) to functions with b-bit output (b = 1 in the CFL model). We allow the players to receive up to b − 1 bits of information from an all-powerful benevolent Helper who can see all the input. Extending results of Babai, Nisan, and Szegedy (1992) to this model, we construct families of explicit functions for which Ω(n/c^{k}) bits of communication are required to find the “missing bit,” where n is the length of each player’s input and k is the number of players. As a consequence we settle the problem of separating the one-way vs. multiround communication complexities (in the CFL sense) for k ≤ (1 − ϵ) log n players, extending a result of Nisan and Wigderson (1991) who demonstrated this separation for k = 3 players. As a byproduct we obtain Ω(n/c^{k}) lower bounds for the multiparty complexity (in the CFL sense) of new families of explicit boolean functions (not derivable from BNS).

∗Department of Computer Science, University of Chicago, 1100 East 58th Street, Chicago, IL 60637. e-mail: laci@cs.uchicago.edu. Supported in part by NSA grant MSPR-96G-184

†Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, IL 60637. e-mail: hayest@math.uchicago.edu. Supported in part by an NSF Graduate Fellowship.

‡Department of Computer Science, Northeastern Illinois University, 5500 N. St. Louis Avenue, Chicago, IL 60625-4699. e-mail: pgkimmel@neiu.edu

The proofs exploit the interplay between two concepts of multicolor discrepancy; discrete Fourier analysis is the basic tool. We also include an unpublished lower bound by A. Wigderson regarding the one-way complexity of the 3-party pointer jumping function.

1 Introduction

1.1 Brief summary

Communication complexity is an abstract model of computation which focuses on the cost of inter-processor communication. It has been linked to a number of models of computation; it appears to be at the heart of complexity questions, especially in highly parallel models (shallow circuits) [13, 14, 25, 6, 20], space-bounded computation (including the related models of decision trees and branching programs) [8, 5, 11], and hardness results required for the construction of pseudorandom generators for shallow circuits [17] and for space-bounded computation [5]. Nisan applied communication complexity to threshold circuits with no depth restriction [19].

Lower bounds in communication complexity pose difficult questions; the multiparty model, introduced by Chandra, Furst, and Lipton [8], is notoriously hard. The strongest known lower bounds in the CFL [8] multiparty model were given by Babai, Nisan, and Szegedy [5], where two families of explicit functions were shown to require Ω(n/c^{k}) communication. Here n is the length of the input, k is the number of players and 2 ≤ c ≤ 4 is a constant. We note that the value of c for one of these functions was subsequently improved by Chung and Tetali [9] from 4 to 2.

The multiparty communication model we consider extends the CFL model in two ways: the output to be computed has b bits (b = 1 in the CFL model); and the players receive “help:” a message of at most b − 1 bits from an all-powerful benevolent Helper who can see all the input. The help, of course, makes lower bound proofs more difficult.

Extending results of [5], we find strong (Ω(n/c^{k})) lower bounds on the communication cost of the “missing bit” for families of explicit functions with long outputs. Here n is the length of the input each player “misses,” k is the number of players, and the output is up to n bits long.

Our main motivation was an application of these lower bounds to the original CFL model (boolean output): we extend a result of Nisan and Wigderson [20] on the separation of one-way vs. multiround communication complexity from three players to any constant number of players (in fact up to k ≤ (1 − ϵ) log n players).

As a by-product, we obtain Ω(n/c^{k}) lower bounds for the k-party communication complexity of interesting new families of boolean functions, including the “trace of matrix product mod 2” function. The importance of such results lies in the wide variety of applications of multiparty lower bounds that has been based on the Ω(n/c^{k}) lower bounds of [5].

The BNS [5] lower bounds were derived from upper bounds on the discrepancy over cylinder intersections of the two-coloring corresponding to the boolean function in question. We need to extend this technique to multicolor discrepancy. We consider two separate discrepancy concepts (strong and weak) both of which reduce to the ordinary discrepancy in the boolean case. Strong discrepancy is the straightforward combinatorial extension; the concept of weak discrepancy is more subtle and requires characters of finite abelian groups (the Discrete Fourier Transform). Our main technique is the interplay between these two concepts of multicolor discrepancy. A concept closely related to our “weak discrepancy” has previously been introduced in the context of multiparty communication complexity by Grolmusz [12].

1.2 Multiparty Communication with Help

Following Chandra, Furst, and Lipton [8], in all models to be considered we adopt the following basic assumptions and notation.

Players A_{1}, …, A_{k} wish to collaboratively evaluate the function f : X_{1}×⋯× X_{k} → B on input x⃗ = (x_{1}, …, x_{k}). Note that in [8], the range B is {0, 1}; here we shall allow arbitrary finite sets B (of variable size.) The function f is known to each player, and Player A_{i} sees all pieces of the input except x_{i}. We say that A_{i} misses x_{i} ∈ X_{i}. The players communicate by broadcasting messages to all other players. Let P (x⃗) be the string of messages broadcast by the players on input x⃗. P is said to compute f correctly if f(x⃗) is fully determined by P (x⃗) (i. e. f(x⃗) is a function of P (x⃗).) The communication complexity of f, denoted by C(f), is the number of bits to be communicated under the best communication protocol, on the worst input: C(f) = min_{P} max_{x⃗}|P (x⃗)|.

Our players will be aided by a “Helper” who can see the entire input and broadcasts a message H(x⃗) to the players before they begin to communicate. By sending b := log |B| bits, the Helper could announce the function value; therefore, we restrict the Helper to sending r ≤ b − 1 bits.

In this model, a protocol P is a collection of protocols in the previous sense (without help): a protocol P^{j} for each possible help message j. The output of the protocol on input x⃗ is (j, P^{j}(x⃗)), where j = H(x⃗) is the help message for the given input. As before, we require the output to fully determine the value of the target function.

Definition 1.1 Let the space of inputs be X = X_{1} × ⋯ × X_{k}. A protocol with help consists of two functions: the Help function H : X → R, where R is a finite set, and a function P : R → P, where P denotes the set of k-party protocols over X (without help).

Let f be a function with domain X. If there is a function g such that for every input x⃗, f(x⃗) = g(H(x⃗), P (H(x⃗))(x⃗)), then we say that (H, P) computes f. In this case we call (H, P) a communication protocol for f, with help from the set R.

We denote the set of such protocols (H, P) by P^{help}(R).

Definition 1.2 The cost of a communication protocol with help, (H, P) is the combined length of the longest message pair (j, s), where j = H(x⃗) is the help message, and s = P (H(x⃗))(x⃗) is the communication string sent by the players.

The communication complexity of f with help, denoted by C^{help}(r, f), is the minimum cost of a protocol with r bits of help for f.

In most but not all cases we assume r = b − 1 and suppress r in the notation: C^{help}(f) :=C^{help}(b − 1, f). (A notable exception is described in Section 9.3.)

Remark 1.3 Another reasonable definition for the cost of a protocol with help would be the maximum length of a Help string, log |R|, plus the maximum cost of a protocol P^{j}. In fact, this definition was used in a preliminary version of this paper. However, all our results hold using the stronger Definition 1.2. We are grateful to one of the referees for suggesting this modification.

1.3 Main Results

Our main result is the following Ω(n) lower bound on the complexity of multiparty communication with help for a family of explicit functions.

Theorem 1.4 There exists an NC-computable class of functions {f_{n,b,k} : n ≥ b ≥ 1, k ≥ 2} where f_{n,b,k} is a function of k n-bit arguments with b-bit output such that C^{help}(f_{n,b,k}) ≥ Ω(n/c^{k}), for some constant c > 1.

Remark 1.5 In the statement above, NC denotes, as usual, the class of functions computable by a uniform family of polynomial-size boolean circuits of polylogarithmic depth (this is a subclass of P, the class of polynomial-time computable functions). In fact, the function GIP_{q,s,k} which will be used to establish the theorem (see Definition 4.11) is computable with bounded fan-in boolean circuits of depth O(log n log k). In particular, it is in NC^{1} for constant k. The same remark applies to Theorem 1.7 below. As we shall see, these lower bounds hold in the randomized and distributional (random input) models as well. We do not know any AC^{0} family of functions satisfying a similar lower bound.

As an application, we generalize a result of Nisan and Wigderson [20].

Definition 1.6 A special case of the standard communication model is one-way communication, in which each player may speak only once, and they proceed in a specified order.

Nisan and Wigderson [20] demonstrate an exponential gap between the power of three-party one-way protocols for boolean functions depending on which player speaks first. We extend their result to 3 ≤ k ≤ (1 − ϵ) log n players.

Theorem 1.7 There exists an NC-computable class of boolean functions {g_{n,k} : n ≥ 1, k ≥ 2} where g_{n,k} is a function of k n-bit arguments such that the oneway communication complexity of g_{n,k} when Player k speaks first is Ω(\sqrt{n}/c^{k}), for some constant c > 1, and the one-way communication complexity of g_{n,k} when any other player speaks first is O(log n).

This result resolves a problem which was open even for k = 4, and complements another separation result (one-way vs. oblivious, [4, 21]).

As a by-product of this work, we obtain a new family of explicit boolean functions whose k-party communication complexity satisfies the BNS [5] lower bounds Ω(n/c^{k}).

Definition 1.8 The trace of matrix product mod 2 function, TMP_{2,d,k}, takes k square (d × d) (0, 1)-matrices as inputs, and returns the trace of their product modulo 2.

Theorem 1.9 TMP_{2,\sqrt{n},k} has k-party communication complexity Ω(n/k^{2}2^{k}). (n is the number of bits each player misses.)

1.4 Organization of the Paper

Section 2 introduces two notions of discrepancy for multivalued functions, and derives a basic inequality between them (Lemma 2.9). Theorem 8.2 exhibits an inequality relating the two notions of discrepancy in the opposite direction.

In Section 3 we link these discrepancies, considered over the family of cylinder intersections, to communication complexity with help. The key lemma to our complexity lower bounds is Lemma 3.3.

Theorem 1.4 and Theorem 1.9 are proved in Section 4, which investigates the discrepancy of multilinear functions over a finite field, extending the results of [5] on the “generalized inner product” (GIP) function. The key result of this section is a rather general upper bound on the discrepancy of multilinear functions over cylinder intersections (Theorem 4.6).

In Section 5, we obtain similar discrepancy bounds for the “multiplicative coset of sum” (MCS) function, extending the results of [5] on the “quadratic character of sum” function. Section 7 shows how to compute a subclass of the MCS functions in polynomial time.

Following Nisan and Wigderson, in Section 6 we apply our results to one-way communication complexity, proving Theorem 1.7. A more technical statement appears as Corollary 6.3.

In Section 9 we reproduce three Ω(n) lower bounds for two-party communication with help (yielding in each case Ω(\sqrt{n}) lower bounds on three-player one-way complexity for functions with O(log n) communication complexity if the order of players is changed).

The subject of Section 9.1 is the MCS function. In Section 9.2 we reproduce a result of Nisan and Wigderson [20] on hash-functions in our framework. That result provided the initial motivation to this paper.

Section 9.3 gives an exposition of an unpublished result of Avi Wigderson: a lower bound for the pointer-jumping function to which the discrepancy approach is not applicable.

A preliminary version of this paper appeared in STOC ’98 [3].

2 Multicolor Discrepancy

Discrepancy is usually discussed in the context of two-colorings. We need a discrepancy concept for any function f : X → B (coloring with |B| colors).

Let f be a function, f : X → B, and let S ⊆ X. If B = {±1}, then the common meaning of the discrepancy of f on S is the sum | ∑_{x∈S} f(x)|. Our concept of strong discrepancy generalizes this notion to arbitrary sets B. Another, weaker generalization of the 2-color discrepancy suggests itself in the case when B is a finite abelian group.

After defining both types of multicolor discrepancy, we prove that they are closely related. We will make good use of this relationship in Section 4.

Definition 2.1 For a function f : X → B, (the “B-coloring of X”), a subset S ⊆ X and y ∈ B, we define the excess γ(y) of color y in S under coloring f by

γ(y) := (|f^{−1}(y) ∩ S| − |S|/|B|) /|X|.  (1)

We define the strong discrepancy of f in S by

Γ(f, S) := max_{y∈B} |γ(y)|  (2)

Definition 2.2 (strong discrepancy for set systems) For a set system F over the universe X, we define the strong discrepancy of f over F by

Γ(f, F) := max_{S∈F} Γ(f, S).

For the definitions of weak discrepancy, we require elementary facts about characters of finite abelian groups (see, for example, [1]).

Definition 2.3 Let G be a finite abelian group with m elements, with operation + and identity element 0. A character of G is a homomorphism from G to the multiplicative group of complex roots of unity. The characters of G form a finite group under elementwise multiplication, which is denoted by Ĝ. The identity element of Ĝ is the principal character, χ_{0}, defined by χ_{0}(g) = 1 for all g ∈ G.

The following Proposition lists some basic facts about characters we will use.

Proposition 2.4 Let G be a finite abelian group.

1. |Ĝ| = |G|. (Indeed, Ĝ ≅ G, but we will not use this.)

2. For any 0 ≠ g ∈ G, ∑_{χ∈Ĝ} χ(g) = 0.

3. For any χ_{0} ≠ χ ∈ Ĝ, ∑_{g∈G} χ(g) = 0.

We define the concept of “weak discrepancy” using characters, for colorings f : X → G, where G is a finite abelian group.

Definition 2.5 (weak discrepancy) For a function f : X → G, a subset S ⊆ X and a character χ ∈ Ĝ, we define the weak χ-discrepancy of f in S by

Γweak_{χ}(f, S) := \frac{1}{|X|} |∑_{x∈S} χ(f(x))| .  (3)

We define the weak discrepancy of f in S by

Γ^{weak}(f, S) := \frac{1}{m − 1} ∑_{χ∈Ĝ,χ≠χ_{0}} Γweak_{χ}(f, S).  (4)

Remark 2.6 The definition of Γweak_{χ}(f, S) generalizes a multicolor discrepancy concept introduced by V. Grolmusz [12]. In our language, Grolmusz considers the case when G is cyclic (which would suffice for our applications as well) and makes a specific choice of χ: χ(i) = ω^{i}, where ω is the m-th root of unity minimizing |1 + ω|. Rather than specifying a particular character, we consider the average over all non-principal characters, Γ^{weak}. This allows us to prove the crucial inequality (5) linking strong and weak discrepancies for arbitrary functions.

Definition 2.7 (weak discrepancy for set systems) For a set system F over universe X, we define the weak discrepancy of f over F by

Γ^{weak}(f, F) := max_{S∈F} Γ^{weak}(f, S).

Remark 2.8 It is easy to see that the inequality Γweak_{χ}(f, S) ≤ m Γ(f, S) holds (see Proposition 8.1). From this, it is immediate that Γ^{weak}(f, S) ≤ m Γ(f, S), justifying the terms “weak” and “strong” discrepancy. Theorem 8.2 will improve this bound. Here, however, we are interested in a somewhat surprising inequality in the opposite direction.

Lemma 2.9 Let G be a finite abelian group with m elements, f : X → G a function, and S ⊆ X. Then

Γ(f, S) ≤ (1 − 1/m) Γ^{weak}(f, S).  (5)

Remark 2.10 This inequality provides the tool for turning upper bounds on weak discrepancy into the upper bounds on strong discrepancy we need for our communication complexity lower bounds (see Lemma 3.3 below).

First we derive an expression for the weak discrepancy in terms of the γ(y)’s.

Proposition 2.11 For any S ⊆ X and any χ ∈ Ĝ, χ ≠ χ_{0}, we have

Γweak_{χ}(f, S) = |∑_{y∈G} χ(y)γ(y)| .  (6)

Proof: Consider equation (3). Reindex the summation by the values y = f(x) ∈ G:

Γweak_{χ}(f, S) = \frac{1}{|X|} |∑_{y∈G} χ(y)|f^{−1}(y) ∩ S||

= |∑_{y∈G} χ(y) (γ(y) + \frac{|S|}{m|X|})| .

Since ∑_{y∈G} χ(y) = 0, the |S|/(m|X|) terms cancel.

Notation 2.12 The function δ : G → {0, 1} is defined by

δ(g) = \{ \begin{matrix}1 & if g = 0 \\ 0 & otherwise. \end{matrix}

Proof of Lemma 2.9: Fix z ∈ G. Then γ(z) = ∑_{y∈G} γ(y)δ(y − z). From Proposition 2.4, it follows that, for every g ∈ G, δ(g) = \frac{1}{m} ∑_{χ∈Ĝ} χ(g). (This is the Fourier

expansion of δ.) Hence

|γ(z)| = |\frac{1}{m} ∑_{y∈G} ∑_{χ∈Ĝ} γ(y)χ(y − z)|

= |\frac{1}{m} ∑_{y∈G} ∑_{χ≠χ_{0}} γ(y)χ(y − z)| ,

because ∑_{y∈G} γ(y) = 0. Now, by the multiplicativity of χ, this is equal to

= |\frac{1}{m} ∑_{χ≠χ_{0}} χ(−z) ∑_{y} γ(y)χ(y)|

≤ \frac{1}{m} ∑_{χ≠χ_{0}} |∑_{y} γ(y)χ(y)| ,

by the triangle inequality, observing that |χ(−z)| = 1. By Proposition 2.11, the above expression equals:

= \frac{1}{m} ∑_{χ≠χ_{0}} Γweak_{χ}(f, S)

= \frac{m − 1}{m} Γ^{weak}(f, S).

(The last step is the definition of Γ^{weak}.) Since Γ(f, S) is defined (Definition 2.1) as the maximum of |γ(y)|, the proof is complete.

3 Communication with Help vs.

Multicolor Discrepancy over Cylinder Intersections

Definition 3.1 Let X = X_{1} ×⋯×X_{k}. A subset S ⊆ X is called a cylinder in the i^{th} dimension if membership in S does not depend on the i^{th} coordinate. A subset of X is called a cylinder intersection if it is an intersection of cylinders. We shall use C to denote the set of all cylinder intersections in X (with respect to the given Cartesian decomposition X = X_{1} × … × X_{k}).

As in the boolean case (cf. [5, Lemma 2.2]), upper bounds on multicolor discrepancy over cylinder intersections yield lower bounds on communication complexity in the “communication with help” model. This remains true even in the distributional sense:

Definition 3.2 The ϵ-distributional communication complexity of f with help, denoted by C^{help,ϵ}(f), is the minimum cost of a protocol with help that computes f correctly on at least a (1 − ϵ)-fraction of X.

Lemma 3.3 Let f : X → B be a function. For 0 ≤ ϵ < 1/2,

C^{help,ϵ}(f) ≥ log (\frac{1/2 − ϵ}{Γ(f, C)})

Proof: Let γ := C^{help,ϵ}(f). Let g be a function that agrees with f on at least a (1 − ϵ)-fraction of X, such that g is computed by a protocol (H, P) of cost γ. Let E := {x ∈ X|f(x) = g(x)}, so that by our choice of g, |E| ≥ (1 − ϵ)|X|. For each help message j, and communication string s, let X(j, s) denote those inputs in X which cause help message j and communication string s to be sent. In other words, X(j, s) = H^{−1}(j) ∩ (P^{j})^{−1}(s). Let E(j, s) = E ∩ X(j, s).

Choose a help message j and a communication string s that maximize

|E(j, s)| − \frac{(P^{j})^{−1}(s)}{|B|}.

If we sum this quantity over all pairs (j, s), the left term contributes |E|, since the sets E(j, s) form a partition of E, while the right term contributes −|X||R|/|B|, since for each choice of j, the sets (P^{j})^{−1}(s) partition X. Since there are at most 2^{γ} pairs (j, s), the maximum of the quantity under consideration is at least (|E| − |X||R|/|B|)2^{−γ}.

Since the pair (j, s) determines g, g is constant on X(j, s), and so f is constant on E(j, s). As observed in [5], the set (P^{j})^{−1}(s) must be a cylinder intersection. Hence,

Γ(f, C) ≥ \frac{1}{|X|} (|E(j, s)| − \frac{(P^{j})^{−1}(s)}{|B|})
≥ (|E|/|X| − |R|/|B|)2^{−γ}
≥ (1 − ϵ − 1/2)2^{−γ},

where the last step uses the fact that |R|/|B| ≤ 1/2, part of the definition of communication with help. Taking logarithms,

C^{help,ϵ}(f) = γ ≥ log (\frac{1/2 − ϵ}{Γ(f, C)}) ,

as claimed.

Remark 3.4 It would be reasonable to relax the restriction that the Helper can send at most b − 1 bits of information, and merely require that |R| ≤ |B| − 1. In this case, the proof of Lemma 3.3 implies that

C^{help,ϵ}(f) ≥ log (\frac{1 − (|R|/|B|) − ϵ}{Γ(f, C)}) ,

Remark 3.5 In [5], an upper bound on the maximum volume of a homogeneous cylinder intersection suffices for the lower bound on deterministic communication complexity. While a discrepancy bound implies a bound on this volume, the full power of the discrepancy bounds is only needed in [5] for the distributional result. In contrast, for the “communication with help” model, we need bounds on the strong discrepancy even for deterministic complexity.

4 The Discrepancy of Multilinear Functions

In this section, we extend the techniques of [5] to prove upper bounds on the weak discrepancy for a large class of functions which includes their “generalized inner product” function, and the “trace of matrix product” function, both of which we will define later.

Definition 4.1 Let V be a vector space over a field 𝔽. A function f : V^{k} → 𝔽 is k-linear if whenever we fix k − 1 of the k input vectors, the resulting function g : V → 𝔽 is a vector space homomorphism.

Our main tool is the following lemma, which was inspired by Lemma 2.3 of [5]. This result relates the weak discrepancy of a multilinear function over an arbitrary cylinder intersection to its weak discrepancy over the entire input space.

Lemma 4.2 Let X_{1}, X_{2}, …, X_{k}, G be finite abelian groups. Let X = X_{1} × ⋯ × X_{k}. Let f : X → G be a homomorphism in each coordinate, let χ be a character of G, and for each i ∈ {1, …, k} let ϕ_{i} : X → G be the characteristic function of a cylinder in the i^{th} dimension. Then

| E_{x∈X} χ(f(x))ϕ_{1}(x) ⋯ ϕ_{k}(x)| ≤ ( E_{x∈X} χ(f(x)))^{2^{1−k}} ,  (7)

where the expectation is taken with respect to the uniform distribution over X.

Remark 4.3 A direct imitation of the BNS [5] proof does not seem to work for this result. Instead, we present Lemma 4.4, a rather technical generalization of Lemma 4.2 to which an extension of the BNS argument is applicable.

Lemma 4.4 Let X_{1}, X_{2}, …, X_{k}, G be finite abelian groups and Ω a probability space. Let X = X_{1} × ⋯ × X_{k}. For each λ ∈ Ω, let f^{λ} : X → G be a homomorphism in each coordinate, let χ^{λ} be a character of G, and for each i ∈ {1, …, k} let ϕ_{i}^{λ} : X → G be the characteristic function of a cylinder in the i^{th} dimension. Then

| E_{λ∈Ω,x∈X} χ^{λ}(f^{λ}(x))ϕ_{1}^{λ}(x) ⋯ ϕ_{k}^{λ}(x)| ≤ ( E_{λ∈Ω,x∈X} χ^{λ}(f^{λ}(x)))^{2^{1−k}} , (8)

where the expectation is taken with respect to the uniform distribution over X^{k} and the given probability measure over Ω.

Note 4.5 Throughout the proof, we will omit the superscript λ, which should be assumed everywhere, whether λ is bound or free. The space Ω of events λ is necessary for the inductive step.

Proof: First let us see that the expression

E_{λ∈Ω,x∈X} χ(f(x))

is always real-valued and in the interval [0, 1]. Fix some λ ∈ Ω and u ∈ X_{2} × ⋯ × X_{k}. By hypothesis, the function f^{u} : X_{1} → G defined by f^{u}(x) = f(x, u) is a homomorphism. Hence the composition χ ∘ f^{u} is a character of X_{1}. Therefore E_{x∈X_{1}}χ(f(x, u)) is either 1 or 0 according to whether χ∘f^{u} is or is not the principal

character, which establishes the claim. This shows that the desired inequality is well-defined.

We proceed by induction on k. For k = 1, the result is trivial.

Let k > 1. For readability, we will omit the arguments to the ϕ_{i}, which are the same as the arguments to χ(f()). Since ϕ_{k} does not depend on x_{k}, and |ϕ_{k}| ≤ 1, we observe that

| E_{λ∈Ω} E_{x∈X} χ(f(x))ϕ_{1} … ϕ_{k}|

≤ E_{λ∈Ω} E_{x̃∈X_{1}×···×X_{k−1}} | E_{x_{k}∈X_{k}} χ(f(x̃, x_{k}))ϕ_{1} … ϕ_{k−1}| .

Henceforth we will denote X_{1} × ⋯ × X_{k−1} by X̃.

Now we make use of the Cauchy-Schwarz inequality in the form |E(z)|^{2} ≤ E(|z|^{2}).

E_{λ∈Ω} E_{x̃∈X̃} | E_{x_{k}∈X_{k}} χ(f(x̃, x_{k}))ϕ_{1} … ϕ_{k−1}|

≤ ( E_{λ∈Ω} E_{x̃∈X̃} | E_{x_{k}∈X_{k}} χ(f(x̃, x_{k}))ϕ_{1} … ϕ_{k−1}|^{2})^{1/2} .

Expressing the squared term using complex conjugation, we obtain

( E_{λ∈Ω} E_{x̃∈X̃} (( E_{u∈X_{k}} χ(f(x̃, u))ϕ_{1}^{u} … ϕ_{k−1}^{u}) \overline{( E_{v∈X_{k}} χ(f(x̃, v))ϕ_{1}^{v} … ϕ_{k−1}^{v})}))^{1/2} ,

where ϕ_{i}^{u} stands for ϕ_{i}(x̃, u), and ϕ_{i}^{v} = ϕ_{i}(x̃, v). Since \overline{χ(f(x̃, v))} = χ(f(x̃, −v)), and the ϕ_{i}^{v} are {0, 1}-valued, this expression may be rewritten as

( E_{λ∈Ω} E_{x̃∈X̃} E_{u,v∈X_{k}} χ(f(x̃, u − v))ϕ_{1}^{u}ϕ_{1}^{v} … ϕ_{k−1}^{u}ϕ_{k−1}^{v})^{1/2} ,

Next we switch the order of summation in the last expression. Define Ω̃ to be the space of events (λ, u, v), where u and v are distributed uniformly in X_{k}, and λ, u, v are independent. For each λ̃ = (λ, u, v) ∈ Ω̃ and x̃ ∈ X̃, define f λ̃(x̃) := f^{λ}(x̃, u − v) and ϕλ̃ ; i(x̃) := ϕ_{i}^{λ}(x̃, u)ϕ_{i}^{λ}(x̃, v). Notice that, for fixed λ̃, f λ̃ is a (k − 1)-linear function in x̃, and that ϕλ̃ ; i is a {0, 1}-valued function which does not depend on the i^{th} coordinate of x̃. This allows us to apply the inductive hypothesis, using Ω̃ for our new probability space. After re-reindexing, and noting that the difference u−v is uniformly distributed in X_{k}, we obtain the desired result. Thus

( E_{λ∈Ω} E_{x̃∈X̃} E_{u,v∈X_{k}} χ(f(x̃, u − v))ϕ_{1}^{u}ϕ_{1}^{v} … ϕ_{k−1}^{u}ϕ_{k−1}^{v})^{1/2}

= ( E_{λ̃∈Ω̃} E_{x̃∈X̃} χ^{λ}(f λ̃(x̃))ϕλ̃ ; 1 … ϕλ̃ ; k−1)^{1/2}

≤ ( E_{λ̃∈Ω̃} E_{x̃∈X̃} χ^{λ}(f λ̃(x̃)))^{2^{1−k}}

= ( E_{λ∈Ω} E_{u,v∈X_{k}} E_{x̃∈X̃} χ(f(x̃, u − v)))^{2^{1−k}}

= ( E_{λ∈Ω} E_{x∈X} χ(f(x)))^{2^{1−k}} .

Theorem 4.6 Let q be a prime power and X_{1}, …, X_{k} finite dimensional vector spaces over 𝔽_{q}, the field of q elements. Let X = X_{1}×…×X_{k}, and let f : X → 𝔽_{q} be a k-linear function. Then

Γ^{weak}(f, C) ≤ ( Pr_{u∈X̃}[∀x ∈ X_{1} f(x, u) = 0])^{2^{1−k}} ,  (9)

where X̃ := X_{2} × ⋯ × X_{k}. (As before, C denotes the set of cylinder intersections over X.)

Proof: The left hand side of inequality (7) is exactly the normalized weak discrepancy Γweak_{χ}(f, S), where S is a cylinder intersection with characteristic function ϕ_{1} ⋯ ϕ_{k}. Lemma 4.2 establishes the inequality

Γweak_{χ}(f, C) ≤ ( E_{x∈X} χ(f(x)))^{2^{1−k}} .  (10)

Suppose that χ ≠ χ_{0}; in this case we claim that the right hand sides of Equations (9) and (10) are equal. To see this, we observe that

E_{x∈X} χ(f(x)) = E_{u∈X̃} E_{x∈X_{1}} χ(f(x, u)).

The inner expectation is 0 except when f(·, u) is identically zero, in which case it is 1. Hence the right hand side is simply Pr_{u∈X̃}[∀x ∈ X_{1} f(x, u) = 0]. Averaging over all non-principal characters χ yields the desired inequality.

4.1 Application: Lower bounds for TMP and GIP

Theorem 4.6 shows that, to get a lower bound on communication complexity with help for a multilinear function, it suffices to give an upper bound on the probability that a related vector-valued function has value zero. The “trace of matrix product” (TMP) and “generalized inner product” (GIP) functions, which we will define shortly, have the “typical” property that the associated vector-valued functions are “reasonably uniform.” In the case of TMP, the associated function is the matrix product function. In the case of GIP, the associated function is the kfold componentwise product function. Because these vector-valued functions have large ranges, “reasonable uniformity” is enough to prove good upper bounds on the probability that the function outputs the zero vector.

Definition 4.7 Let q be a prime power, and let d be a positive integer. Let M be the space of d × d matrices over 𝔽_{q}. The function TMP_{q,d,k} : M^{k} → 𝔽_{q} is defined by

TMP_{q,d,k}(A_{1}, A_{2}, …, A_{k}) := Tr(A_{1} · A_{2} ⋯ A_{k})

and is called the trace of matrix product function. (The trace of a matrix (a_{i,j}) is ∑ a_{i,i}.)

Corollary 4.8 C^{help}(TMP_{q,d,k}) ≥ Ω(n/k^{2}2^{k}), where n = d^{2} log q is the number of bits each player misses.

Remark 4.9 Specializing to the case q = 2 we obtain Theorem 1.9.

Proof: We first introduce a notation for the matrix product function.

Notation 4.10 Let q be a prime power, and let d be a positive integer. Let M = M(d, q) be the space of d × d matrices over 𝔽_{q}. The function MP_{q,d,k} : M^{k} → M is defined by

MP_{q,d,k}(A_{1}, A_{2}, …, A_{k}) := A_{1} · A_{2} ⋯ A_{k}

and is called the matrix product function.

The result will follow from the following three claims, each of which is easy to see.

Consistent with our previous notation, let X_{1}, …, X_{k} each denote a copy of M = M(d, q). Let X̃ denote the space X_{2} × … × X_{k} of inputs visible to Player

1. As before, all probabilities will be taken with respect to the uniform distribution over the space indicated under the “Pr” symbol. Claim. Let u ∈ X̃.

((∀x ∈ X_{1}) TMP_{q,d,k}(x, u) = 0) ⇔ (MP_{q,d,k−1}(u) = 0).

Claim.

Pr_{u∈X̃}[MP(u) = 0] ≤ (k − 1) · Pr_{x∈M}[rankx ≤ d − d/(k − 1)].

Claim. For every integer r ≥ 0.

Pr_{x∈M}[rankx ≤ r] ≤ \binom{d}{r}q^{−(d−r)^{2}}.

Combining Theorem 4.6 and these three claims, we have:

Γ^{weak}(TMP_{q,d,k}, C) ≤ ((k − 1)\binom{d}{⌈d/(k − 1)⌉}q^{−⌈d/(k−1)⌉^{2}})^{2^{1−k}} .

Applying Lemmas 2.9 and 3.3 and simplifying, we obtain

C^{help}(TMP_{q,d,k}) ≥ 2^{(1−k)} (⌈d/(k − 1)⌉^{2} log q − log ((k − 1)\binom{d}{⌈d/(k − 1)⌉}))−1.

Substituting n = ⌈d^{2} log q⌉, and observing that the negative terms on the right hand side are negligible when n > 2^{k}, we conclude that

C^{help}(TMP_{q,d,k}) ≥ Ω (\frac{n}{k^{2}2^{k}} ) .

Next we define the “generalized inner product” function over 𝔽_{q}, and prove a lower bound on its communication complexity with help.

Definition 4.11 For a prime power q, positive integers s and k, we define the generalized inner product

GIP_{q,s,k} : (𝔽_{q}^{s})^{k} → 𝔽_{q}

for x_{1}, …, x_{k} ∈ 𝔽_{q}^{s} by

GIP_{q,s,k}(x_{1}, …, x_{k}) = ∑_{i=1}^{s} x_{1,i} · x_{2,i} ⋯ x_{k,i}.

Corollary 4.12 C^{help}(GIP_{q,s,k}) ≥ Ω(n/4^{k}), where n = ⌈s log q⌉ is the number of bits each player misses. Moreover, if q ≥ k^{1+ϵ} for some fixed ϵ > 0, then

C^{help}(GIP_{q,s,k}) ≥ Ω(n/2^{k}),

Proof: First we define the componentwise product function.

Definition 4.13 For a prime power q, positive integers s and k, we define the componentwise product

CWP_{q,s,k} : (𝔽_{q}^{s})^{k} → 𝔽_{q}^{s}

for x_{1}, …, x_{k} ∈ 𝔽_{q}^{s} by

(CWP_{q,s,k}(x_{1}, …, x_{k}))_{i} = x_{1,i} · x_{2,i} ⋯ x_{k,i}.

Consistent with our previous notation, let X_{1}, …, X_{k} each denote the vector space 𝔽_{q}^{s}. Let X̃ denote the space X_{2} × … × X_{k} of inputs visible to Player 1. As always, all probabilities will be taken with respect to the uniform distribution over the space indicated below the Pr symbol.

The result will follow from the following two claims, both of which are easy to see. Claim. Let u ∈ X̃.

((∀x ∈ X_{1}) GIP_{q,s,k}(x, u) = 0) ⇔ (CWP_{q,s,k−1}(u) = 0).

Claim.

Pr_{u∈X̃}[CWP_{q,s,k−1}(u) = 0] = (1 − (1 − 1/q)^{k−1})^{s}.

Applying Theorem 4.6 and Lemmas 2.9 and 3.3, we obtain

C^{help}(GIP_{q,s,k}) ≥ −2^{(1−k)} (s log (1 − (1 − 1/q)^{k−1})) − 1.

Applying the inequality 1 − x < e^{−x} for x = (1 − 1/q)^{k−1}, we obtain the lower bound

C^{help}(GIP_{q,s,k}) ≥ Ω (\frac{s}{c(q)^{k}} ) = Ω (\frac{n}{c(q)^{k} log q} )

where c(q) := 2q/(q − 1) and n = ⌈s log q⌉. Note that when q = 2, c(q)^{k} log q = 4^{k}, and we are done. When 2 < q, we have c(q) ≤ 3, so as long as 2 < q < 2^{(4/3)^{k}}, c(q)^{k} log q < 4^{k}. Since q > 2^{(4/3)^{k}} implies q ≥ k^{1+ϵ}, it will suffice to prove the second part of the corollary.

Assume q ≥ k^{1+ϵ}. In this case, we may apply the inequality

(1 − 1/q)^{k−1} ≥ 1 − (k − 1)/q

to obtain

C^{help}(GIP_{q,s,k}) ≥ 2^{1−k}s(log q − log(k − 1)) − 1
≥ 2^{1−k}s\frac{ϵ}{1 + ϵ} log q − 1
= Ω(n/2^{k}).

This completes the proof of Corollary 4.12.

5 The Discrepancy of the Multiplicative Coset of Sum

In this section, we prove upper bounds on the multicolor discrepancy of another class of explicit functions over cylinder intersections. The analysis of these “multiplicative coset of sum” (MCS) functions depends on A. Weil’s character sum estimates, through a lemma proved by Babai-Nisan-Szegedy [5]. The MCS functions are more difficult to compute than the GIP and TMP functions (cf. Section 7). Besides their mathematical appeal, the significance of the MCS functions may lie in their potential to work beyond log n players.

Notation 5.1 For q a prime power, let 𝔽_{q} denote the field of q elements, and let 𝔽_{q}^{×} denote 𝔽_{q} \ {0}, the multiplicative group of 𝔽_{q}. For x = (x_{1}, …, x_{k}) ∈ 𝔽_{q}^{k}, let Σx denote ∑_{i=1}^{k} x_{i}.

Definition 5.2 Let q be a prime power, let u divide q − 1, and let s := (q − 1)/u. Then the mapping y ↦ y^{s} maps the cyclic group 𝔽_{q}^{×} onto its (unique) subgroup G of index s and order u.

We define the multiplicative coset of sum function

MCS_{q,u,k} : (𝔽_{q})^{k} → G

for x = (x_{1}, …, x_{k}) ∈ 𝔽_{q}^{k}, by

MCS_{q,u,k}(x) = \{ \begin{matrix}∗ & if Σx = 0 \\ (Σx)^{s} & otherwise, \end{matrix}  (11)

where the “∗” stands for “undefined.” Our discrepancy bound will hold for any mapping of the undefined entries to G.

Remark 5.3 Note that G is in one-to-one correspondence with the cosets by the (unique) subgroup H of order s of 𝔽_{q}^{×}. In fact, we really only care about which coset of H contains Σx. The discrepancy bound we give holds for any encoding of the cosets.

Lemma 5.4 Let C be the set of cylinder intersections in 𝔽_{q}^{k}. Then

Γ(MCS_{q,u,k}, C) ≤ 3q^{−2^{−k}} + 1/q.

Our chief tool in proving this lemma is a special case of Lemma 2.6 of [5], which involves multiplicative characters.

Definition 5.5 A multiplicative character χ of 𝔽_{q} is a homomorphism of 𝔽_{q}^{×} to the group of complex roots of unity. The principal character χ_{0} is the character that maps all of 𝔽_{q}^{×} to the value 1. Characters are usually extended to the entire field by setting χ(0) = 0.

Lemma 5.6 (BNS [5], Lemma 2.6) Let q be a prime power, and let ψ : 𝔽_{q} → ℂ be a non-principal multiplicative character. For any positive integer k and any cylinder intersection S in 𝔽_{q}^{k}, we have

|∑_{x∈S} ψ(Σx)| ≤ 3 · q^{k−2^{−k}}.

Remark 5.7 Note that the proof of Lemma 5.6 is based on a character sum estimate by A. Weil (cf. [23]).

Proof of Lemma 5.4: Let χ be a non-principal character of G. To simplify notation, set f = MCS_{q,u,k}. We shall estimate the weak χ-discrepancy of f over any cylinder intersection S ⊆ 𝔽_{q}^{k}. Let ψ be the multiplicative character of 𝔽_{q} defined by ψ(y) = χ(y^{s}) for y ∈ 𝔽_{q}^{×} and ψ(0) = 0. Since the map y ↦ y^{s} maps 𝔽_{q}^{×} onto G, it follows that ψ is not the principal character.

Let V = {x ∈ 𝔽_{q}^{k} : Σx = 0}. Note that |V | = q^{k−1}.

We have

Γweak_{χ}(f) = q^{−k} |∑_{x∈S} χ(f(x))| ≤ q^{−k} (|V | + |∑_{x∈S} χ((Σx)^{s})|) ,

because the two expressions differ only for x ∈ V, in which case χ((Σx)^{s}) = 0 and |χ(f(x))| = 1.

The right hand side can be estimated using Lemma 5.6:

q^{−k} |∑_{x∈S} χ((Σx)^{s})| = q^{−k} |∑_{x∈S} ψ(Σx)| ≤ 3 · q^{−2^{−k}}.

Combining the last two inequalities we obtain

Γweak_{χ}(f) ≤ 3 · q^{−2^{−k}} + 1/q.

Since this inequality holds for every χ ≠ χ_{0} and every cylinder intersection S, it follows by Lemma 2.9 that the right hand side bounds the strong discrepancy as well, completing the proof of Lemma 5.4.

The lower bound for the communication complexity with help of MCS follows directly from Lemmas 3.3 and 5.4:

Theorem 5.8 C^{help,ϵ}(MCS_{q,u,k}) ≥ (log q)/2^{k} + log(1/2 − ϵ) − 2.

6 Bounds on One-way Communication via Help

In this section, we apply the concept of “communication with help” to derive a bound on one-way complexity of a special class of functions, when a particular player speaks first. The basic trick is inspired by Nisan and Wigderson, [20], where the 3-party case is considered. We extend their result to k ≤ (1 − ϵ) log n players.

In a one-way communication protocol, the players each speak exactly once, in a prespecified order. For our result, the exact order in which the players speak will not matter; we will only need that the first player to speak is only allowed to speak once. With this in mind, we define ^{i}C(f) to be the communication complexity of f when Player i speaks first, and only once. ^{i}C_{1}(f) is the one-way communication complexity of f when Player i speaks first, and the other players speak once in some order.

Now we define the class of functions for which we will derive one-way communication bounds. Nisan and Wigderson [20] used the following construction to obtain a k-party boolean function from a (k − 1)-party multibit-output function.

Constuction 6.1 Let B = {0, 1}^{b}, and let f : X_{2} × … × X_{k} → B be any function. We define f̃: {1, …, b} × X_{2} × … × X_{k} → {0, 1} by f̃(i, x_{2}, …, x_{k}) = f(x_{2}, …, x_{k})_{i}. In other words, Player 1’s input specifies a single bit of the output of f.

Lemma 6.2 Let f, f̃be as described above. Then

1C(f̃) ≥ min {b, C^{help}(f)/b} .

Proof: Suppose we are given a communication protocol that computes f, that begins with Player 1 sending at most b − 1 bits, but never speaking again. We use this protocol to construct a (k − 1)-party protocol with help to compute the function f itself. In this protocol, on input (x_{2}, …, x_{k}), the Helper sends the same message Player 1 would send in the protocol for f̃. Players 2 through k now compute f̃(i, x_{2}, …, x_{k}) for each possible value of i, using the given protocol. After this, every bit of f(x_{1}, …, x_{k}) has been found, and at most b ·^{1}C(f̃) bits of communication have been used.

Corollary 6.3 Let f = GIP_{2^{\sqrt{n}},\sqrt{n},k−1}, and let f̃ be defined as above. Then 1C(f̃) = Ω(\sqrt{n}/2^{k}), while for 2 ≤ i ≤ k, ^{i}C_{1}(f̃) ≤ log n + 1. Also, f̃ can be computed by bounded fan-in boolean circuits of depth O(log n log k).

Proof: The lower bound on ^{1}C(f̃) follows directly from Corollary 4.12 and Lemma 6.2. The upper bound on^{i}C_{1}(f̃) for 2 ≤ i ≤ k is achieved by the protocol in which Player i first sends all the bits of x_{1}, then Player 1 sends the output.

To obtain a small-depth circuit, observe that two elements of 𝔽_{2^{\sqrt{n}}} can be multiplied in depth O(log n). Therefore a single component of the componentwise product can be computed in depth O(log n log k). Adding the terms takes only an additional O(log n) depth.

Theorem 1.7 is an immediate consequence of Corollary 6.3.

A similar result holds for the MCS function:

Corollary 6.4 Let f = MCS_{q,u,k} and let f̃ be defined as above. For all n, one can choose u and q such that f̃is polynomial time computable, log q = Θ(n) and 1C(f̃) ≥ Ω(\sqrt{n}/2^{k/2}), while for 2 ≤ i ≤ k, ^{i}C_{1}(f̃) ≤ O(log n) for any q and u.

Proof: We choose u to be a prime power, and q to be an integer power of u, such that n = ⌈log q⌉ ≈ 2^{k}(log u)^{2}. The lower bound on ^{i}C_{1}(f̃) follows from Theorem 5.8 and Lemma 6.2.

To establish the claim that f̃ is polynomial-time computable, we first need to address the issue of how the input and output of MCS should be represented by binary strings. We defer the discussion of this to Section 7. Our choice of parameters makes the group G the multiplicative subgroup of a subfield of 𝔽_{q}; it will follow by Theorem 7.3 that f̃is polynomial-time computable.

7 MCS: How Explicit?

The function MCS_{q,u,k} given in Definition 5.2 is clearly computable in polynomial time ((k−1) additions and O(log q/u) multiplications in 𝔽_{q}), assuming 𝔽_{q} is given explicitly as a log q-bit part of the input.

What is not reasonable about this view of the function, however, is, that the output is encoded by log q bits while its information content is only log u bits. Optimal encoding of the output (hashing) makes no difference in the context of communication complexity where the players have unlimited computational power. However, it does make a difference when talking about Turing-complexity such as polynomial time.

In this section we show how to accomplish the optimal encoding in polynomial time for the MCS function under certain restrictions on the parameters.

The special case we consider is when G is the multiplicative group of a subfield 𝔽_{u+1} of 𝔽_{q} and the output is optimally encoded as an element of the subfield.

We shall say that 𝔽_{q} is explicitly represented if we are given an irreducible polynomial f ∈ 𝔽_{p}[x] of degree w over 𝔽_{p} where p is the characteristic and q = p^{w}. In this case, we treat 𝔽_{q} as the field 𝔽_{p}[x]/(f). In this case the element ϑ of 𝔽_{q} corresponding to the polynomial x is a generator of 𝔽_{q}, i. e., 𝔽_{q} = 𝔽_{p}[ϑ] and f is the minimal polynomial of ϑ over 𝔽_{p}. The powers 1, ϑ, ϑ^{2}, …, ϑ^{w−1} form a basis of 𝔽_{q} over 𝔽_{p}.

We make the polynomial f part of the input, thereby increasing the length of the input by at most a factor of 2.

An optimal encoding of the elements of a subfield K ⊂ 𝔽_{q} is an encoding by binary strings of length ⌈log |K|⌉.

Lemma 7.1 Let 𝔽_{q} be explicitly represented, where q = p^{w}. Let r | w and let K be the (unique) subfield of 𝔽_{q} of order p^{r}. Then an optimal encoding of the elements of K can be computed in polynomial time ((log q)^{O(1)}).

Proof: Let v := |K| = p^{r}. The trace function, Tr : 𝔽_{q} → K is defined by Tr(g) = g + g^{v} + g^{v^{2}} + … + g^{v^{t−1}}, where t = w/r. The trace function is K-linear and it is easily seen to be onto (cf. Ireland and Rosen [15, p. 145]). Consequently, the elements Tr(1), Tr(ϑ), Tr(ϑ^{2}), …, Tr(ϑ^{w−1}) span K as a linear space over 𝔽_{p}. Take the first r of these that are linearly independent over 𝔽_{p} to be the “canonical” basis for K over 𝔽_{p}, and represent every element of K by its coordinates with respect to this basis. This can be converted to a binary string of length ⌈w log q⌉ = ⌈log |K|⌉.

We now define the “explicit MCS function” (EMCS):

Definition 7.2 Let q be a prime power, let k, r, t be positive integers, let w = rt, let q = p^{w}, let u = p^{r} − 1, and let s = (q − 1)/u. We define the function EMCS_{q,u,k} : {0, 1}^{(k+1)⌈w log p⌉} → {0, 1}^{⌈r log p⌉} as follows. The first ⌈w log p⌉ bits define a degree w polynomial f ∈ 𝔽_{p}[x]. If this polynomial is reducible, output 1. Otherwise, we represent 𝔽_{q} as 𝔽_{q} = 𝔽_{p}[x]/(f), and interpret the next k⌈w log p⌉ bits as x_{1}, …, x_{k} ∈ 𝔽_{q}, in the usual way. Compute MCS_{q,u,k}(x_{1}, …, x_{k}) and output its canonical representation as a string of length ⌈r log p⌉ in accordance with Lemma 7.1.

Theorem 7.3 Let q, u, k be as in Definition 7.2. Then EMCS_{q,u,k} is polynomialtime computable.

Proof: Berlekamp’s algorithm [7] decides whether a polynomial of degree d over 𝔽_{p} is irreducible, in time O(d^{2} log^{2} d log log d log p) (cf. Rabin [22]).

The other computations require only a polynomial number of arithmetic operations over 𝔽_{p}, since we can use repeated squaring when evaluating the trace function.

This completes the justification of Corollary 6.4.

To make our output a bit more appealing, we might wish to represent the subfield by an irreducible polynomial. This, too, can be done in polynomial time, as shown in [2].

8 Appendix A: Strong versus Weak Discrepancies

We now prove the inequality that justifies the terms “strong” and “weak” for the two kinds of discrepancies (see Remark 2.8).

We use the notation introduced in Definition 2.3.

Proposition 8.1 For any S ⊆ X and any χ ∈ Ĝ, χ ≠ χ_{0}, we have Γweak_{χ}(f, S) ≤ m · Γ(f, S), where m = |G|.

Proof: Follows from Definition 2.1 and Proposition 2.11.

From Proposition 8.1, it follows by averaging that m · Γ(f, S) is also an upper bound on Γ^{weak}(f, S). However, we can improve this upper bound by a \sqrt{m − 1} factor.

Theorem 8.2 Γ^{weak}(f, S) ≤ (m/\sqrt{m − 1}) · Γ(f, S).

Proof: By Proposition 2.11, we have

Γ^{weak}(f, S) = \frac{1}{(m − 1)} ∑_{χ≠χ_{0}} |∑_{y∈G} χ(y)γ(y)| ,

where the outer sum is taken over all nonprincipal characters χ of G, and the excess, γ(y) is defined in Definition 2.1. By the Cauchy-Schwarz inequality we obtain

(Γ^{weak}(f, S))^{2} ≤ \frac{1}{(m − 1)} ∑_{χ≠χ_{0}} |∑_{y∈G} χ(y)γ(y)|^{2} .

We rewrite this inequality, and proceed to simplify it.

(m − 1)(Γ^{weak}(f, S))^{2} ≤ ∑_{χ≠χ_{0}} |∑_{y∈G} χ(y)γ(y)|^{2}

= ∑_{χ≠χ_{0}} ∑_{y,z∈G} χ(y − z)γ(y)γ(z)

= ∑_{χ≠χ_{0}} ( ∑_{{y,z∈G \atop y≠z}} χ(y − z)γ(y)γ(z) + ∑_{y∈G} γ(y)^{2}) .

Reversing the order of summation and simplifying, we have

= ∑_{{y,z∈G \atop y≠z}} −γ(y)γ(z) + (m − 1) ∑_{y∈G} γ(y)^{2}

= \frac{1}{2} ∑_{{y,z∈G \atop y≠z}}(γ(y) − γ(z))^{2} ≤ m^{2}Γ(f, S)^{2},

where the last inequality follows by Proposition 2.11 and by choosing α = 2 and a_{i} = γ(y_{i})/Γ(f, S) in Proposition 8.3 below.

Proposition 8.3 Let A = {a_{1}, …, a_{m}} be a multiset of real numbers such that, for all i, |a_{i}| ≤ 1. Then for α ≥ 1, we have

h(A) := ∑_{1≤i<j≤m} |a_{i} − a_{j}|^{α} ≤ ⌊m^{2}/4⌋ · 2^{α}.

Proof: For such a multiset A, let N^{+}(A) denote the multiplicity of +1 in A, and let N^{−}(A) denote the multiplicity of −1 in A. The claimed upper bound for h(A) is achieved if {N^{−}(A), N^{+}(A)} = {⌊m/2⌋, ⌈m/2⌉}. Otherwise, suppose without loss of generality that N^{−}(A) < N^{+}(A). Let b = min{a ∈ A | a > −1}. Then replacing b by −1 yields a new multiset A′ of size m, such that h(A′) > h(A). This shows that h(A) is maximal if and only if {N^{−}(A), N^{+}(A)} = {⌊m/2⌋, ⌈m/2⌉}, proving the Proposition.

9 Appendix B: Two Players with Help

For the case of two players, cylinder intersections correspond to cartesian products (“rectangles”) which are much easier to handle. This fact allows us to derive a strong upper bound on the discrepancy of MCS with two players without requiring mathematics as deep as Weil’s character sum estimates. We need only some basic facts about the Fourier transform over finite abelian groups (cf. [1]).

We also reproduce the three-player boolean function one-way lower bound of Nisan and Wigderson using the two-player model with help. Finally, with the author’s permission, we include a lower bound for the one-way complexity of the three-player pointer jumping function due to A. Wigderson.

9.1 MCS for Two Players with Help

Let f = MCS_{q,u,2} where q is a prime power and u|q − 1 (cf. Section 5). Let s = (q − 1)/u. Recall the definition of this function:

f(x, y) := \{ \begin{matrix}∗ & if x + y = 0 \\ (x + y)^{s} & otherwise, \end{matrix}

where the “∗” stands for “undefined.” As before, the discrepancy bound will hold for any mapping of the undefined entries to the range G := {z^{s} | z ∈ 𝔽_{q}^{×}}.

To obtain an upper bound on the discrepancy of f we will use the following result about Fourier transforms over finite abelian groups (see [1, Thms. 4.1 and 6.8]).

Theorem 9.1 Let q be a prime power, s | q − 1, and S_{1}, S_{2} ⊆ 𝔽_{q}. For each z ∈ 𝔽_{q}^{×}, let N_{z} be the number of solutions (x, y) ∈ S_{1} × S_{2} to the equation

(x + y)^{s} = z.  (12)

Then, for each z ∈ 𝔽_{q}^{×},

|N_{z} − |S_{1}||S_{2}|s/q| < \sqrt{|S_{1}||S_{2}|q}.  (13)

Let C be the set of cylinder intersections (rectangles) in 𝔽_{q} × 𝔽_{q}.

Lemma 9.2 Γ(f, C) < 2q^{−1/2}.

Proof: Let V = {(x, y) ∈ 𝔽_{q} × 𝔽_{q} : x + y = 0}. Let S be a rectangle in 𝔽_{q} × 𝔽_{q}, i. e., S = S_{1} × S_{2}, where S_{1}, S_{2} ⊆ 𝔽_{q}. Let z ∈ G.

From Definition 2.1 and Theorem 9.1, we have

γ(z) = |\frac{|f^{−1}(z) ∩ S| − |S|/u}{|X|}| ≤ \frac{1}{q^{2}} (|N_{z} − \frac{|S|}{u}| + |V |)
≤ \frac{1}{q^{2}} (|N_{z} − \frac{|S| (q − 1)}{uq}| + \frac{|S|}{uq} + q)
< \frac{1}{q^{2}} (\sqrt{|S|q} + \frac{|S|}{uq} + q)
≤ q^{−1/2} + (uq)^{−1} + q^{−1}
< 2q^{−1/2}.

Thus, by definition, Γ(f, C) ≤ 2q^{−1/2}.

Plugging this into Lemma 3.3 and choosing q to be an n-bit prime yields the following theorem:

Theorem 9.3 C^{help}(f) ≥ n/2 − 2.

Applying Lemma 6.2 to f, we find

Corollary 9.4 ^{1}C(f̃) ≥ \sqrt{n/2} − 1, while when i = 2 or i = 3, ^{i}C_{1}(f̃) ≤ log n + 1.

This result is analogous to the three-player one-way bound of Nisan and Wigderson [20] for their “bits of hash value” function (see Section 9.2).

9.2 Universal Hash Functions and the Nisan–Wigderson One-way Bound

Nisan and Wigderson [20] prove an Ω(\sqrt{n}) lower bound for the 3-party one-way complexity of the “bits of hash value” (BHV) function derived from universal families of hash functions. Our limited understanding of their proof served as the initial motivation for this paper. In this section we present a version of their proof in the formal framework of “communication with help.” We replace their somewhat cryptic handling of certain conditional probabilities with the analysis via multicolor discrepancy. Nisan and Wigderson invoke the “Leftover Hash Lemma” by Y. Mansour, N. Nisan, and P. Tiwari [18] to estimate a conditional probability; we rephrase this idea in terms of a multicolor discrepancy bound.

Definition 9.5 Let X = {0, 1}^{2n}, Y = Z = {0, 1}^{n}. We may think of X as a 2-universal family of hash functions, x : Y → Z (see Carter and Wegman [10]).

Let 1 ≤ ℓ ≤ n. Let

f_{ℓ} : X × Y → {0, 1}^{ℓ}

be defined by f_{ℓ}(x, y) = the first ℓ bits of x(y). We shall also use the notation HV_{n,ℓ} = f_{ℓ} (for ℓ-truncated n-bit hash value).

Recall that Construction 6.1 creates a function f̃_{ℓ} : {1, …, ℓ} × X × Y → {0, 1} defined by f̃_{ℓ}(i, x, y) := f_{ℓ}(x, y)_{i} = (x(y))_{i}. We shall also use the notation BHV_{n,ℓ} = f̃_{ℓ} (“bits of hash value”). The main result explained in this section is the following 3-player one-way lower bound.

Theorem 9.6 (Nisan, Wigderson [20]) ^{1}C(BHV_{n,\sqrt{n/2}}) ≥ \sqrt{n/2}.

Following Nisan and Wigderson [20] we employ the “Leftover Hash Lemma” [18]. In our framework, this lemma implies an upper bound on the discrepancy of f_{ℓ} over the set of cylinder intersections (rectangles) in X × Y.

Lemma 9.7 (“Leftover Hash Lemma,” Mansour, Nisan, Tiwari [18]) Let Y_{0} ⊆ Y, Z_{0} ⊆ Z, X_{0} ⊆ X, and p = |Z_{0}|/|Z|. Then

| Pr[x(y) ∈ Z_{0} | x ∈ X_{0}, y ∈ Y_{0}] − p| ≤ \sqrt{p|X|/(|X_{0}||Y_{0}|)}.

Lemma 9.8 Γ(f_{ℓ}, C) ≤ 1/2^{(n+ℓ)/2}.

Proof: Let S be a cylinder intersection in X ×Y. For two dimensions, observe that cylinder intersections correspond to cartesian products of subsets, so there exist X_{S} ⊆ X and Y_{S} ⊆ Y such that S = X_{S} × Y_{S}.

In the notation of Definition 2.1, let α ∈ {0, 1}^{ℓ} maximize |γ(α)| for the function f_{ℓ} and the set S. Then

Γ(f_{ℓ}, S) = |γ(α)| = \frac{1}{|X||Y |} ||f_{ℓ}^{−1}(α) ∩ S| − \frac{|S|}{m}| .

Let Z_{0} := {z ∈ {0, 1}^{n} | the first ℓ bits of z are α} so p = 2^{−ℓ}. With this notation,

Γ(f_{ℓ}, S) = \frac{1}{|X||Y |} · ||f_{n}^{−1}(Z_{0}) ∩ S| − \frac{|S|}{m}|
= \frac{|S|}{|X||Y |} ( Pr_{(x,y)∈S}[x(y) ∈ Z_{0}] − p)

(Here f_{n}(x, y) = x(y), untruncated.) Since S = X_{S} × Y_{S}, we infer from Lemma 9.7 that

Γ(f_{ℓ}, S) ≤ \sqrt{\frac{p|X|}{|S|}} · \frac{|S|}{|X||Y |} = \sqrt{\frac{p|S|}{|X||Y |^{2}}}
≤ \sqrt{p/|Y |} = 2^{−(ℓ+n)/2}.

This bound and Lemma 3.3 imply the Ω(n) lower bound for the 2-party communication complexity with help of the HV function:

Theorem 9.9 C^{help}(HV_{n,ℓ}) ≥ (n + ℓ)/2 − 1.

Now an application of Lemma 6.2 to f̃_{ℓ} = BHV_{n,ℓ} with ℓ = ⌈\sqrt{n/2}⌉, together with Theorem 9.9, yield Theorem 9.6.

9.3 One-way separation for pointer jumping

In this section we present an unpublished result of A. Wigderson, analyzing the one-way complexity of the 3-party “pointer jumping” function via two-party communication with help.

Definition 9.10 For a positive integer n, we set [n] := {1, …, n}. Let m_{0}, m_{1}, …, m_{k} be positive integers. The k-party composition function takes as input a k-tuple (f_{1}, …, f_{k}) of functions, where f_{1} : [m_{0}] → [m_{1}], f_{2} : [m_{1}] → [m_{2}], …, f_{k} : [m_{k−1}] → [m_{k}], and returns their composition, f_{k} ∘ f_{k−1} ∘ … ∘ f_{1}. In the special case when m_{0} = 1, m_{k} = 2, this function is boolean, and is called the k-party pointer jumping function.

We consider the 3-party pointer jumping function, where n = m_{2} = m_{1}^{2}. In this case, the inputs f_{1}, f_{2}, f_{3} can be represented by strings of log n/2, \sqrt{n} log n/2, n bits, respectively (for convenience, we assume all quantities are integral).

Theorem 9.11 (Wigderson) For the 3-party pointer jumping function, where n = m_{2} = m_{1}^{2}, the one-way communication complexity is Ω(\sqrt{n}) when the players speak in the order 1, 2, 3, but is O(log n) for any other order.

Proof: We follow Wigderson’s outline [24]. For the k-party pointer jumping function, if the communication order is not 1, 2, …, k, then there exist i < j such that Player j speaks before Player i. Let Player j’s message encode the value f_{j−1}∘ …∘f_{1}(1). This takes at most log m_{j−1} bits. Since Player i is given f_{j}, …, f_{k}, she can compute the output without further communication. This shows that the oneway communication complexity for pointer jumping is O(log n) except possibly for the ascending communication order, where n is the bit-length of the longest input.

Now consider the 3-party pointer jumping function with m_{1} = \sqrt{n} and m_{2} = n. As in Section 6, we relate the one-way communication complexity of the 3-party pointer jumping function to a restricted version of communication complexity with help for a 2-party composition function. Specifically, we consider the communication game where Player 2 sees input f_{3}, Player 3 sees input f_{2}, and Player 1 sees both functions. (There is no longer an input f_{1}.) The goal is to compute the composition f_{3} ∘ f_{2}. Communication occurs as in the two-way “communication with help” model, with Player 1 acting as Helper, except that after the help message, communication is one-way, with Player 2 speaking before Player 3. Additionally, we will restrict Player 1’s help message to have length less than \sqrt{n}/4.

Suppose there were a one-way communication protocol of cost less than \sqrt{n}/6 for the 3-party pointer jumping function (computing f_{3} ∘ f_{2} ∘ f_{1}). From this, we construct a protocol of cost less than n/6 for the 2-party composition function (computing f_{3} ∘ f_{2}): Player 1’s message is used as the help message. For each 1 ≤ i ≤ m_{1}, Player 2 sends the message he would have sent if f_{1}(1) were i. The total cost is less than n/6, and Player 3 can compute f_{3} ∘ f_{2}(i) for every i, and so can output the answer.

We now develop the machinery that will allow us to deduce lower bounds for the two-party problem described above.

Definition 9.12 Let Y be a set and let n be a positive integer. For any n-tuple y ∈ Y^{n} and non-negative integer r, we define the Hamming ball of radius r centered at y, B_{r}(y), to be the set of all points z ∈ Y whose Hamming distance from y is less than or equal to r. We say that S is a near-Hamming ball centered at y if there exists an r such that B_{r}(y) ⊆ S ⊆ B_{r+1}(y).

Notation 9.13 For the rest of this Appendix, we adopt the following notational conventions: m_{1}, m_{2}, m_{3} are arbitrary positive integers, f is an element of [m_{2}]^{[m_{1}]}, g, g′, g_{0} are elements of [m_{3}]^{[m_{2}]}, S, S_{0}, T are subsets of [m_{3}]^{[m_{2}]}, b is a function b : [m_{2}]^{[m_{1}]} → [m_{3}]^{[m_{1}]}. Moreover, when f and g are selected at random, f is always assumed to be uniformly distributed over [m_{2}]^{[m_{1}]} and g uniformly distributed over S.

Definition 9.14 We say that (b, S) form a standard pair if there exists a function g_{0} such that for every f, b(f) = g_{0} ∘ f, and such that S is a near-Hamming ball centered at g_{0}.

Definition 9.15 We set

p(b, S, f) := Pr_{g}[b(f) = g ∘ f],

and

p(b, S) := Pr_{f,g}[b(f) = g ∘ f].

The following combinatorial lemma is our main technical tool.

Lemma 9.16 Let k be a positive integer. Then max{p(b, S) | |S| = k} is attained by the standard pairs (b, S) such that |S| = k.

Proof: Claim 1: Fix b and suppose there exists g_{0} such that for all f, b(f) = g_{0} ∘ f. Then p(b, S) is maximized, subject to the constraint |S| = k, when S is any near-Hamming ball centered at g_{0}.

To see this, fix g and consider Pr_{f}[b(f) = g ∘ f]. This probability is (1 − d(g, g_{0})/m_{2})^{m_{1}}, where d(g, g_{0}) denotes the Hamming distance between g and g_{0}. Since this function is decreasing, the result is clear.

Claim 2: For all pairs (b, S), for all g_{0}, there exists S_{0} such that |S_{0}| = |S| and for all f, p(b, S, f) ≤ p(b_{0}, S_{0}, f), where b_{0} denotes the function b_{0}(f) = g_{0} ∘ f.

The proof is by a shifting argument. The following construction incrementally modifies the pair (b, S) in m_{2} rounds, to produce the output (b_{0}, S_{0}). At the end of each iteration, for every f, p(b, S, f) has increased or remained the same, and |S| also remains the same. From this, the claim follows. Here is the construction:

for j := 1 to m_{2} T := ∅ for g ∈ S

Let g′ be defined by g′(i) = \{ \begin{matrix}g_{0}(j) & if i = j \\ g(i) & otherwise. \end{matrix}

if g′ ∉ S then add g′ to T

else add g to T

endfor

S := T

Redefine b so that, for all f, \{ \begin{matrix}b(f)(i) = g_{0}(j) when f_{2}(i) = j \\ b(f)(i) is unchanged otherwise. \end{matrix}

endfor

It is clear that the output (b_{0}, S_{0}) produced by this algorithm satisfies |S_{0}| = |S| and for every f, b_{0}(f) = g_{0} ∘ f. To see that, for any f, p(b, S, f) does not decrease at step j, we observe that after round j, the number of functions g ∈ S such that g(j) = g_{0}(j) is at least as great as the number of instances of any previous value of g(j); in particular, for any f, i such that f(i) = j, it is at least as great as the number of instances that g(j) = b(f)(i). This proves Claim 2.

Now, suppose we are given a pair (b, S) maximizing p(b, S). By Claim 2, we can replace this by a pair (b_{0}, S_{0}), where there exists g_{0} such that b is defined by b(f) = g_{0} ∘ f, without decreasing p(b, S, f) for any f. In particular, p(b, S) must still be maximal. Now, by Claim 1, we know that S_{0} must be a near-Hamming ball, and so (b_{0}, S_{0}) is a regular pair.

Remark 9.17 One can show that, under the conditions of Lemma 9.16, the only pairs (b, S) attaining the maximum value are the standard pairs.

Corollary 9.18 For all b, S such that |S| = k, we have

p(b, S) ≤ e^{−m_{1}/4} + 2^{5m_{2}/6}(m_{3} − 1)^{m_{2}/4}/k.

Proof: By Lemma 9.16, we may assume that b is defined by b(f) = g_{0} ∘ f for some g_{0}. Suppose g ∈ S has Hamming distance i from g_{0}. Then

Pr_{f}[g ∘ f = g_{0} ∘ f] = (1 − i/m_{2})^{m_{1}} ≤ e^{−im_{1}/m_{2}}.

It follows that

p(b, S) ≤ \frac{1}{k} ∑_{i=0}^{m_{2}} |S_{i}|e^{−im_{1}/m_{2}},

where S_{i} denotes the set of elements of S at Hamming distance i from g_{0}. Those terms for which i ≥ m_{2}/4 contribute at most ke^{−m_{1}/4} total to the sum. On the other hand, there are exactly \binom{m_{2}}{i}(m_{3} − 1)^{i} functions g at Hamming distance i from g_{0}. It follows, since the value of the binary entropy function H(1/4) = 0.8113... < 5/6, that the number of functions g with Hamming distance at most m_{2}/4 from g_{0} is less than 2^{5m_{2}/6}(m_{3} − 1)^{m_{2}/4}. Adding these estimates completes the proof.

We now complete the proof of Theorem 9.11. Recall that, on input (f_{2}, f_{3}), Player 1 sends help message H(f_{2}, f_{3}). Let M(h)(f_{3}) denote the message Player 2 would send on input f_{3} under help message h.

For any input pair (f_{2}, f_{3}), let h = H(f_{2}, f_{3}) denote the message sent by the Helper, Player 1, and let s = M(h)(f_{3}) denote the message sent by Player 2. For such a pair of messages (h, s), we define sets

X_{h,s} := {(f_{2}, f_{3}) | h = H(f_{2}, f_{3}), s = M(h)(f_{3})}
S_{h,s} := M(h)^{−1}(s) = {f_{3} | s = M(h)(f_{3})}.

In the one-way communication protocol with help, after the message pair (h, s) has been sent, Player 3 computes the output f_{3} ∘ f_{2}. Hence the communication protocol defines, for each message pair (h, s), a function b_{h,s} : [m_{2}]^{[m_{1}]} → [m_{3}]^{[m_{1}]}, defined by b_{h,s}(f_{2}) := Player 3’s output given input f_{2}, when message h is sent by the Helper, and message s is sent by Player 2. (We may assume that the protocol specifies an output for Player 3, even given communication strings which could not be sent for an actual input pair.) Observe that

X_{h,s} ⊆ {(f_{2}, f_{3}) | b_{h,s}(f_{2}) = f_{3} ∘ f_{2}, f_{3} ∈ S_{h,s}},

and thus

|X_{h,s}| ≤ Pr[b_{h,s}(f_{2}) = f_{3} ∘ f_{2}] · m_{2}^{m_{1}} · |S_{h,s}|,

where f_{2} ∈ [m_{2}]^{[m_{1}]} and f_{3} ∈ S_{h,s} are chosen uniformly. It follows, by Corollary 9.18, with m_{1} = \sqrt{n}, m_{2} = n, m_{3} = 2, S = S_{h,s}, b = b_{h,s}, that

|X_{h,s}| ≤ (e^{−\sqrt{n}/4}|S_{h,s}| + 2^{5n/6})n^{\sqrt{n}}

The sets X_{h,s} partition the input space [n]^{[\sqrt{n}]} × [2]^{[n]}. Hence,

2^{n}n^{\sqrt{n}} = ∑_{h,s} |X_{h,s}|
≤ ∑_{h,s}(e^{−\sqrt{n}/4}|S_{h,s}| + 2^{5n/6})n^{\sqrt{n}}.

Now, since for fixed h, the sets S_{h,s} partition [2]^{[n]}, we have

2^{n} ≤ ∑_{h} e^{−\sqrt{n}/4}2^{n} + ∑_{h,s} 2^{5n/6}.

It follows that either the number of help messages h is at least 2^{\sqrt{n}(log e/4)−1} or the number of message pairs (h, s) is at least 2^{n/6−1}. As discussed earlier, this proves that the original 3-party protocol had cost at least \sqrt{n}/6. This proves Theorem 9.11.

Acknowledgment.

We wish to thank Avi Wigderson for allowing us to include his bound for the pointer-jumping function in this paper (Section 9.3).

References

[1] L. Babai. The Fourier Transform and Equations Over Finite Abelian Groups, Lecture Notes, manuscript, version 1.2, December 1989.

[2] L. Babai, T. Hayes. Finding a generator for a subfield of a finite field. Manuscript, 2000. .

[3] L. Babai, T. Hayes, and P. Kimmel. The Cost of the Missing Bit: Communication Complexity with Help. (Preliminary version) 30th ACM STOC (1998) 673–682.

[4] L. Babai, P. Kimmel, and S. V. Lokam. Simultaneous Messages vs. Communication. 12th Symp. Theor. Asp. Comp. Sci., 1995, Springer Lecture Notes in Comp. Sci. 900 (1995) 361–372. Updated version: L. Babai, A. Gál, P. Kimmel, and S. V. Lokam. Simultaneous Messages vs. Communication. SIAM J. Comp., submitted.

[5] L. Babai, N. Nisan, and M. Szegedy. Multiparty Protocols, Pseudorandom Generators for Logspace and Time-Space Trade-offs. J. Comp. Sys. Sci. 45, 1992, 204–232. (Preliminary version: 20th ACM STOC (1988) 539– 550.)

[6] R. Beigel and J. Tarui. On ACC. 32nd IEEE FOCS (1991) 783–792.

[7] E.R. Berlekamp. Factoring polynomials over large finite fields. Math. Comput. 24 (1970) 713–735.

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

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

[10] L. Carter and M. Wegman, Universal Hash Functions. J. Comp. Sys. Sci. 18 (1979) 143–154.

[11] H. D. Gröger, G. Turán. On linear decision trees computing boolean functions. 18th ICALP, Springer Lect. Notes in Comp. Sci. 510 (1991) 707– 719.

[12] V. Grolmusz. Separating the Communication Complexities of MOD m and MOD p Circuits. J. Comp. Sys. Sci. 51 (1995) 307–313. (Preliminary version: 33rd IEEE FOCS (1992) 278–287.)

[13] A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, G. Turán. Threshold circuits of bounded depth. 28th IEEE FOCS (1987) 99–110.

[14] J. Håstad and M. Goldmann. On the Power of Small-Depth Threshold Circuits. Computational Complexity 1 (1991) 113–129.

[15] K. Ireland and M. Rosen. A Classical Introduction to Modern Number Theory. Springer-Verlag, 1982.

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

[17] M. Luby, B. Veličković, and A. Wigderson. Deterministic Approximate Counting of Depth-2 Circuits. Proc. Second Israel Symp. on Theory and Computing Systems, IEEE Comp. Soc. Press, 1993, 18–24.

[18] Y. Mansour, N. Nisan, and P. Tiwari. The Computational Complexity of Universal Hashing. Theor. Comp. Sci. 107 (1993) 121–133.

[19] N. Nisan. The communication complexity of threshold gates. In: Combinatorics, Paul Erdős is Eighty (D. Miklós, T. Szőnyi, V. T. Sós, eds.), Vol. 1. Bolyai Society Mathematical Studies 1, Budapest 1993 (distributed by the A. M. S.), 301–315.

[20] N. Nisan, A. Wigderson. Rounds in Communication Complexity Revisited. SIAM J. Comp. 22 (1993) 211–219. (Preliminary version: 23rd ACM STOC (1991) 419–429.)

[21] P. Pudlák, V. Rödl, and J. Sgall. Boolean Circuits, Tensor Ranks and Communication Complexity. SIAM J. Comp. 26 (1997) 605–633.

[22] M. Rabin, Probabilistic Algorithms in Finite Fields. SIAM J. Comp. 9 (1980) 273–280.

[23] W. M. Schmidt: Equations over Finite Fields: An Elementary Approach. Lect. Notes in Math. 536, Springer 1976.

[24] A. Wigderson. Personal communication. April 20, 1997.

[25] A. C-C. Yao. On ACC and Threshold Circuits. 31st IEEE FOCS (1990) 619–627.