Communication Complexity

The Two-Party Model

In the standard model (Yao, 1979), two players Alice and Bob wish to compute a function f(x, y) where Alice holds x in X, Bob holds y in Y. They communicate bits according to a protocol. The communication complexity of a protocol is the worst-case number of bits exchanged. The communication complexity of f is the minimum over all correct protocols.

Notation: D(f) = deterministic CC, R(f) = randomized CC (two-sided error), R_1(f) = one-sided error.

Deterministic Communication Complexity

Protocol Trees

A deterministic protocol defines a binary tree: internal nodes specify which player speaks and what bit they send (as a function of their input and the transcript so far). Leaves are labeled with f(x,y). A protocol with communication cost c has at most 2^c leaves.

The Communication Matrix

The communication matrix M_f has rows indexed by x, columns by y, with M_f[x,y] = f(x,y). A protocol of cost c partitions M_f into at most 2^c combinatorial rectangles (Cartesian products R = S x T where S is a subset of X, T is a subset of Y), each monochromatic (constant value of f).

Theorem: D(f) = ceil(log_2(number of monochromatic rectangles needed to tile M_f)).

This is the partition number or cover number of the matrix.

Lower Bound Techniques

Fooling Sets

A fooling set for f is a set of pairs {(x_1,y_1), ..., (x_t,y_t)} such that:

f(x_i, y_i) = b for all i (same value)
For all i != j, either f(x_i, y_j) != b or f(x_j, y_i) != b

Theorem: If f has a fooling set of size t, then D(f) >= log_2(t).

Proof: Each (x_i, y_i) must be in a different rectangle. If two pairs (x_i, y_i) and (x_j, y_j) were in the same rectangle R = S x T, then (x_i, y_j) in R would also have value b, contradicting the fooling set property.

Example: EQUALITY on n-bit strings has fooling set {(x,x) : x in {0,1}^n} of size 2^n, giving D(EQ) >= n. Combined with the trivial upper bound, D(EQ) = n + 1.

Rectangle Arguments (Rank Lower Bound)

Theorem: D(f) >= log_2(rank(M_f)) where rank is over the reals.

A monochromatic rectangle contributes a rank-1 submatrix (for 0/1 functions after shifting). The number of rectangles is at least the rank.

Example: INNER-PRODUCT mod 2 has rank 2^n over GF(2), but over the reals, rank(M_{IP}) = 2^n, giving D(IP) >= n. In fact, D(IP) = n + 1.

Log-rank conjecture (Lovasz-Saks, 1988): D(f) = (log rank(M_f))^{O(1)}. This remains open; the best known bound is D(f) = O(sqrt{rank(M_f)} * log rank(M_f)) for specific function classes.

Discrepancy Method

The discrepancy of f with respect to a distribution mu is:

disc(f, mu) = max over rectangles R of |mu(R intersect f^{-1}(0)) - mu(R intersect f^{-1}(1))|

Theorem: R(f) >= log(1/(2 * disc(f, mu))) for any distribution mu.

Low discrepancy means every rectangle is nearly balanced between 0 and 1 inputs, so no single rectangle query can reliably determine f.

Example: INNER-PRODUCT has discrepancy 2^{-n/2} under the uniform distribution, giving R(IP) >= n/2.

Corruption Bound

Strengthens discrepancy: instead of requiring rectangles to be balanced, requires that any large rectangle must contain many "errors."

Randomized Communication Complexity

In the public-coin model, Alice and Bob share a random string. In the private-coin model, each has independent randomness.

Theorem (Newman, 1991): Public-coin and private-coin randomized CC differ by at most O(log n). Specifically, R^{pub}(f) <= R^{priv}(f) <= R^{pub}(f) + O(log n).

Key Results

EQ: D(EQ) = n + 1, but R(EQ) = O(1) (hash x, send hash; check equality)
DISJ (set disjointness): R(DISJ) = Theta(n). This is a foundational result: even randomization does not help for disjointness.
GT (greater-than): D(GT) = n + 1, R(GT) = O(log n)

Set Disjointness Lower Bound

Theorem (Kalyanasundaram-Schnitger, 1992; Razborov, 2003): R(DISJ_n) = Omega(n).

Razborov's proof via information complexity is the cleanest:

Show that computing DISJ on "hard" distributions requires Omega(n) bits of information about the inputs
Information revealed >= communication cost (by definition)

The hard distribution embeds AND on a random coordinate within a mostly-disjoint pair, using a product structure.

Information Complexity

The information complexity IC(f) of a function f is the minimum mutual information between the transcript and the inputs, over all protocols computing f correctly.

Formally: IC_mu(f, epsilon) = min over protocols Pi computing f with error epsilon of I(Pi ; X | Y) + I(Pi ; Y | X), where the information is measured under distribution mu.

Direct Sum via Information Complexity

Theorem: IC(f) <= R(f) (information is at most communication), and R(f) = Theta(IC(f)) in many cases.

Direct sum theorem: To compute f on k independent instances, the communication required is at least k * IC(f, epsilon). This follows because information is additive across independent instances.

Application: The tight lower bound R(DISJ_n) = Omega(n) follows from showing IC(AND, 1/3) = Omega(1) and applying direct sum over n coordinates.

Information vs Communication Gap

There exist functions where IC(f) = o(R(f)), showing that information and communication can differ. The gap is at most exponential: R(f) <= 2^{O(IC(f))}.

Compression conjecture: R(f) = O(IC(f) * polylog(n)). This is open and would have strong consequences for direct sum theorems.

Multiparty Communication Complexity

In the number-on-forehead (NOF) model with k players, player i sees all inputs except x_i. This model is significantly more powerful than the two-party model.

Connections to circuit complexity: Lower bounds in the k-party NOF model for k = log n + 1 players would imply ACC^0 lower bounds (Beigel-Tarui, 1994). Even for 3 players, strong lower bounds remain elusive.

Known results:

Set disjointness in NOF: Omega(n^{1/k} / 2^k) lower bound for k players (Lee-Shraibman)
Generalized inner product (GIP): Omega(n/4^k) for k players (Babai-Nisan-Szegedy)

Applications to Other Areas

Circuit Lower Bounds

Karchmer-Wigderson games (1990): The circuit depth of f equals the communication complexity of the related "search problem" KW(f). This gives:

NC^1 vs P is equivalent to: can the KW game for every function in P be solved with O(log n) communication?
Composition of KW games corresponds to circuit composition

Streaming Lower Bounds

Communication lower bounds directly imply streaming lower bounds. If Alice holds the first half of the stream and Bob holds the second half, any streaming algorithm with memory s implies a communication protocol with cost O(s).

Applications:

Frequency moments F_k require Omega(n^{1-2/k}) space for k > 2 (Alon-Matias-Szegedy, via CC)
Distinct elements require Omega(1/epsilon^2 + log n) space (via CC reductions)
Graph problems in streams: connectivity requires Omega(n) space in one pass (via DISJ)

coN(f) = log(cover_0(M_f)), the minimum over 0-rectangles.

Relationship: D(f) = O(N(f) * coN(f)) -- from the combinatorial rectangle structure. This quadratic relationship is essentially tight.

Quantum Communication Complexity

Quantum communication allows sending qubits and using entanglement.

Key separations:

EQ: Q(EQ) = O(log n) (quantum fingerprinting), compared to R(EQ) = O(1) for randomized -- no separation here
Disjointness: Q(DISJ) = Theta(sqrt{n}) (Aaronson-Ambainis, 2005; Braverman et al.), quadratic improvement over R(DISJ) = Theta(n)
Vector in subspace: Exponential separation between quantum one-way CC and classical (Raz, 1999)

Open Problems

Log-rank conjecture: Is D(f) polynomially related to log(rank(M_f))?
Direct sum for randomized CC: Does R(f^k) = Omega(k * R(f))?
Strong NOF lower bounds for explicit functions with superconstant k players
Exact characterization of quantum vs classical CC for total functions
Resolution of the information-communication compression conjecture