$$

Let $f:=T_1\vee \cdots \vee T_s$ be a size-$s$ DNF. If Andromeda has an input $x$ such that $f(x)=0$ and Orion has an input $y$ such that $f(y)=1$, then they can play the following communication game to find an index $i\in [n]$ on which $x_i\ne y_i$:

• Orion says the index $j\in [s]$ of a term $T_j$ that he makes true;
• Andromeda says the name of $i\in [n]$ of a literal in $T_j$ that she makes false.

This is the Karchmer–Wigderson game for $f$.

General form: circuits give protocols

Andromeda and Orion can play this game in $d$ rounds for any function $f$ that has a depth-$d$ circuit, and the communication cost at each round will be $\le \log s$.¹ Indeed,

• if the top gate is an AND gate $f:=f_1\wedge \cdots \wedge f_s$, then Andromeda can point to a specific $f_j$ it makes false, while Orion makes them all true;
• if the top gate is an OR gate $f:=f_1\vee \cdots \vee f_s$, then Orion can point to a specific $f_j$ it makes true, while Andromeda makes them all false.

This means that if you want to prove a lower bound on constant-depth circuits, all you have to do is to show is a communication lower bound on this game. For example, to prove a size lower bound of $2^{\mathrm{\Omega }\left(\sqrt{n}\right)}$ on ${\mathrm{\Sigma }}^3$ circuits for parity, you only need to show a $\mathrm{\Omega }\left(\sqrt{n}\right)$ communication on the communication game where

• Andromeda has a input $x$ of even parity,
• Orion has an input $y$ of odd parity,
• Orion speaks first, then Andromeda speaks, then Orion says an $i$ such that $x_i\ne y_i$.

Concretely, you might try to do this by contradiction: assume that the protocol takes $o\left(\sqrt{n}\right)$ communication, and find a pair $x,y$ that it fails to distinguish. This type of lower bound is called top-down.

Converse: protocols give circuits

The connection goes the other way: if you can play Karchmer–Wigderson game, then that gives you a small circuit.

In fact, fix any sets of inputs $X,Y\subseteq {\{0,1\}}^n$.² If given any $x\in X$ and $y\in Y$, Andromeda and Orion can find an index $i\in [n]$ on which $x_i\ne y_i$ using $d$ rounds and $\log s$ bits of communication, then there is a ${\mathrm{\Sigma }}^d$ or ${\mathrm{\Pi }}^d$ formula (depending on whether Orion or Andromeda speaks first) of size $\le s^d$ that rejects all of $X$ and accepts all of $Y$.

This is somewhat surprising: indeed, given some input $x$, it’s not clear how you’d use the protocol in a black box to figure whether it is in $X$ or in $Y$. And interestingly, it means that studying Karchmer–Wigderson games is completely equivalent to studying the sizes of constant-depth circuits.

Proof

The proof works by induction on the number of rounds. To make things cleaner, let’s assume that instead of having Andromeda or Orion say the index $i$, this is done by an external observer looking at the transcript of the communication.

Base case ($d=0$). Here, the external observer spits out index $i$ without knowing anything about the inputs. This is only possible if $X$ and $Y$ are separated by a dictator.

Inductive case ($d\ge 1$).

• Suppose Andromeda speaks first, and partition $X$ into subsets $X_1,\dots ,X_s$ according to what she says. By induction, there are ${\mathrm{\Sigma }}^d$ formulas $f_1,\dots ,f_s$ of size $\le s^{d-1}$ such that $f_j$ rejects $X_j$ and accepts $Y$. Then their AND $f_1\wedge \cdots \wedge f_s$ must reject all of $X$ and still accept all of $Y$.
• Symmetrically, if Orion speaks first, then partition $Y$ into subsets $Y_1,\dots ,Y_s$ according to what he says, take some formulas $f_j$ that accept $X$ and reject $Y_j$, then OR them together.

1. The last step will take $\log n$ bits, but most of the time we’re considering sizes $s\ge n$ anyway. ↩

2. Think of them as subsets of $f^{-1}(0)$ and $f^{-1}(1)$. ↩