Let \(X\) and \(Y\) be arbitrary types, let \(g : X \times Y \to \mathrm{Bool}\) (written \(g(x,y)\)), let \(S \subseteq X \times Y\), and let \(\sigma : \mathrm{Bool} \to \mathbb {R}\) send \(\mathrm{false}\) to \(1\) and \(\mathrm{true}\) to \(-1\). Then for every point \((x,y) \in X \times Y\),

where each indicator takes the value \(1\) on its set and \(0\) elsewhere.

Let \(X \times Y\) carry a finite probability space \(\mu \), let \(g : X \to Y \to \mathrm{Bool}\) be a Boolean function, and let \(\gamma \in \mathbb {R}\). If every rectangle \(R \subseteq X \times Y\) satisfies \(\left\lvert \mathrm{disc}_\mu (g, R)\right\rvert \le \gamma \), then \(\gamma \ge 0\).

Let \(p\) be a deterministic Boolean two-party communication protocol on input types \(X\) (Alice) and \(Y\) (Bob), and let \(R \subseteq X \times Y\) be any set. Define the rectangle sign of \(p\) on \(R\) to be \(+1\) when \(p\) outputs \(\mathrm{false}\) at every point of \(R\) and \(-1\) otherwise. Then the rectangle sign has absolute value \(1\).

Let \(p\) be a deterministic two-party communication protocol with Boolean output, over input types \(X\) (Alice) and \(Y\) (Bob). If \(R\) is a leaf rectangle of \(p\) and \((x, y)\) is any point of \(R\), then the rectangle sign of \(R\) agrees with the Boolean sign of the value that \(p\) computes on \((x, y)\): it equals \(+1\) when \(p\) outputs \(\mathrm{false}\) at \((x, y)\) and \(-1\) when \(p\) outputs \(\mathrm{true}\).

Let \(X \times Y\) carry the structure of a finite probability space, let \(p\) be a deterministic two-party communication protocol on inputs \(X\) (Alice) and \(Y\) (Bob) with Boolean output, and let \(R \subseteq X \times Y\). Then \(R\) belongs to the finite set enumerating the leaf rectangles of \(p\) if and only if \(R\) is a leaf rectangle of \(p\).

Let \(X\) and \(Y\) be input types whose product \(X \times Y\) carries a finite probability space, and let \(p\) be a deterministic Boolean two-party protocol over \(X\) (Alice) and \(Y\) (Bob). Write \(\{ R\} \) for the finite collection of leaf rectangles of \(p\), and for each such rectangle assign the sign \(\varepsilon (R) = +1\) if \(p\) outputs \(\mathrm{false}\) at every point of \(R\) and \(\varepsilon (R) = -1\) otherwise. Then for every point \((x,y) \in X \times Y\),

where \(p(x,y)\) denotes the Boolean value returned by running \(p\) on inputs \(x\) and \(y\).

Let \(X\) and \(Y\) be the input types of Alice and Bob, and let \(\mu \) be a finite probability measure on \(X \times Y\). Write \(\sigma \colon \mathrm{Bool} \to \{ \pm 1\} \) for the map sending \(\mathrm{false}\) to \(1\) and \(\mathrm{true}\) to \(-1\). For a deterministic communication protocol \(p\) with Boolean output and a target function \(g \colon X \to Y \to \mathrm{Bool}\), the expected signed correlation between the protocol’s output and the target satisfies

where \(p(x,y)\) denotes the value computed by running \(p\) on \((x,y)\) and \(\varepsilon _\mu (p,g) = \mu \bigl(\{ (x,y) \mid p(x,y) \ne g(x,y)\} \bigr)\) is the distributional error of \(p\) against \(g\) under \(\mu \).

Let \(\mu \) be a finite probability space on \(X \times Y\), let \(p\) be a deterministic Boolean communication protocol with input types \(X\) and \(Y\), and let \(g : X \to Y \to \mathrm{Bool}\). Writing \(\sigma \) for the sign map sending \(\mathrm{false}\) to \(1\) and \(\mathrm{true}\) to \(-1\), the signed bias of \(p\) against \(g\) satisfies

where the sum runs over the (finitely many) leaf rectangles \(R\) of \(p\), the value \(p(x,y)\) is the output of \(p\) on inputs \(x\) and \(y\), the rectangle sign \(s(p,R)\) equals \(+1\) if \(p\) outputs \(\mathrm{false}\) at every point of \(R\) and \(-1\) otherwise, and \(\mathrm{disc}_\mu (g,R) = \mathbb {E}_{(x,y)\sim \mu }[\mathbf{1}_R(x,y)\cdot \sigma (g(x,y))]\) is the discrepancy of \(g\) on \(R\).