60 Communication Complexity — Private Coin Basic
60.1 Overview
This module introduces the private-coin protocol model for two-party communication complexity. A private-coin protocol is a deterministic protocol in which Alice and Bob each hold independent private randomness; correctness is measured by the probability (over the private coins) of producing an incorrect answer on every input pair \((x, y)\).
60.2 Declarations
A private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \) is defined as a deterministic protocol \(\texttt{Deterministic.Protocol}\; (\Omega _X \times X)\; (\Omega _Y \times Y)\; \alpha \). Alice’s message function receives the pair \((\omega _x, x)\) and Bob’s receives \((\omega _y, y)\), so each player’s coin flip is invisible to the other.
The constant output node of a private-coin protocol that immediately returns the value \(a : \alpha \), without any further communication.
Given a function \(f : X \to \Omega _X \to \mathrm{Bool}\) and a continuation \(P : \mathrm{Bool} \to \mathrm{Protocol}\; \Omega _X\; \Omega _Y\; X\; Y\; \alpha \), constructs the protocol node at which Alice sends the bit \(f\, x\, \omega _x\) and execution continues with \(P(\text{bit})\).
Given a function \(f : Y \to \Omega _Y \to \mathrm{Bool}\) and a continuation \(P : \mathrm{Bool} \to \mathrm{Protocol}\; \Omega _X\; \Omega _Y\; X\; Y\; \alpha \), constructs the protocol node at which Bob sends the bit \(f\, y\, \omega _y\) and execution continues with \(P(\text{bit})\).
\(\texttt{rrun}\; p\; x\; y\; \omega _x\; \omega _y\) executes the private-coin protocol \(p\) on inputs \(x \in X\) and \(y \in Y\) with Alice’s private coin \(\omega _x \in \Omega _X\) and Bob’s private coin \(\omega _y \in \Omega _Y\), returning the output \(\alpha \). It is defined by \(p.\mathrm{run}\, (\omega _x, x)\, (\omega _y, y)\).
Let \(p\) be a private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \). Then for all inputs \(x \in X\) and \(y \in Y\) and all coin outcomes \(\omega _x \in \Omega _X\) and \(\omega _y \in \Omega _Y\), the randomized execution of \(p\) equals the deterministic execution of \(p\) on the paired inputs \((\omega _x, x)\) and \((\omega _y, y)\):
A private-coin protocol \(p\) \(\varepsilon \)-satisfies a predicate \(Q : X \to Y \to \alpha \to \mathrm{Prop}\) if for every input pair \((x, y)\),
where \(\mu \) is the product measure on \(\Omega _X \times \Omega _Y\).
A private-coin protocol \(p\) \(\varepsilon \)-computes a function \(f : X \to Y \to \alpha \) if for every input pair \((x, y)\),
This formalises the standard notion of bounded-error private-coin randomized communication complexity.
Let \(p\) be a private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \), each randomness space carrying a measure, let \(f : X \to Y \to \alpha \) be a target function, and let \(\varepsilon \in \mathbb {R}\). Then the proposition that \(p\) approximately computes \(f\) within error \(\varepsilon \) coincides with the proposition that \(p\) approximately satisfies, within error \(\varepsilon \), the predicate that holds of \((x, y, a)\) exactly when \(a = f(x, y)\).