63 Communication Complexity — Private Coin Finite Message
63.1 Overview
This module defines private-coin finite-message protocols as a thin wrapper around deterministic finite-message protocols, where Alice’s input type is augmented with her private randomness space \(\Omega _X\) and Bob’s with \(\Omega _Y\). It provides constructors for Alice and Bob sending steps, an execution function rrun that separates public inputs from private coins, approximate-correctness predicates CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ApproxSatisfies and CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.ApproxComputes, and conversions to and from the binary private-coin protocol type.
63.2 Declarations
A private-coin finite-message protocol over input types \(X\), \(Y\) with private randomness types \(\Omega _X\), \(\Omega _Y\) and output type \(\alpha \) is defined as a deterministic finite-message protocol whose effective input for Alice is \(\Omega _X \times X\) and for Bob is \(\Omega _Y \times Y\).
The leaf node of a private-coin finite-message protocol that produces the constant output \(a : \alpha \), constructed by delegating to the corresponding output constructor of the underlying deterministic finite-message protocol.
Given a function \(f : X \to \Omega _X \to \beta \) (Alice’s message function depending on her public input and private randomness) and a continuation \(P : \beta \to \mathsf{Protocol}\), constructs a protocol node at which Alice sends a \(\beta \)-valued message and execution branches on it.
Given a function \(f : Y \to \Omega _Y \to \beta \) (Bob’s message function depending on his public input and private randomness) and a continuation \(P : \beta \to \mathsf{Protocol}\), constructs a protocol node at which Bob sends a \(\beta \)-valued message and execution branches on it.
\(\texttt{rrun}\, p\, x\, y\, \omega _x\, \omega _y\) executes the protocol \(p\) on public inputs \(x : X\), \(y : Y\) with Alice’s private coin \(\omega _x : \Omega _X\) and Bob’s private coin \(\omega _y : \Omega _Y\), returning an element of \(\alpha \). It is defined by running the underlying deterministic protocol on the paired inputs \((\omega _x, x)\) and \((\omega _y, y)\).
Let \(p\) be a private-coin finite-message protocol over input types \(X\), \(Y\), with private-randomness types \(\Omega _X\), \(\Omega _Y\) and output type \(\alpha \). For all inputs \(x : X\) and \(y : Y\) and all private coins \(\omega _x : \Omega _X\) and \(\omega _y : \Omega _Y\), executing \(p\) with those explicit coins agrees with executing the underlying deterministic finite-message protocol on the paired inputs \((\omega _x, x)\) for Alice and \((\omega _y, y)\) for Bob; that is, both yield the same element of \(\alpha \).
A protocol \(p\) \(\varepsilon \)-satisfies a predicate \(Q : X \to Y \to \alpha \to \mathrm{Prop}\) if for every input pair \((x, y)\),
A protocol \(p\) \(\varepsilon \)-computes a function \(f : X \to Y \to \alpha \) if for every input pair \((x, y)\),
Let \(p\) be a private-coin finite-message protocol over input types \(X\), \(Y\) with private-randomness types \(\Omega _X\), \(\Omega _Y\) and output type \(\alpha \), each of \(\Omega _X\) and \(\Omega _Y\) carrying a measure, let \(f : X \times Y \to \alpha \) be a target function, and let \(\varepsilon \in \mathbb {R}\). Then the proposition that \(p\) \(\varepsilon \)-computes \(f\) coincides with the proposition that \(p\) \(\varepsilon \)-satisfies the predicate \(Q(x,y,a)\) given by \(a = f(x,y)\); that is, the two propositions are equal.
Converts a private-coin finite-message protocol into a binary-tree private-coin protocol by delegating to CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol.
Let \(p\) be a private-coin finite-message protocol with private-randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \), in which each message is an element of an arbitrary finite nonempty type. Fix inputs \(x \in X\) and \(y \in Y\) together with private coins \(\omega _x \in \Omega _X\) and \(\omega _y \in \Omega _Y\). Then converting \(p\) to a binary private-coin protocol leaves its randomized execution unchanged: running the converted protocol on \(x, y\) with coins \(\omega _x, \omega _y\) returns the same element of \(\alpha \) as running \(p\) itself on the same inputs and coins.
Let \(p\) be a private-coin finite-message protocol with private randomness spaces \(\Omega _X\) and \(\Omega _Y\), input types \(X\) and \(Y\), and output type \(\alpha \), in which each message is an element of an arbitrary finite nonempty type \(\beta \) costing \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits. Converting \(p\) into the associated binary private-coin protocol, in which every message is encoded as a string of bits, leaves the worst-case communication complexity unchanged: the complexity of the converted binary protocol equals the complexity of \(p\).
Embeds a binary private-coin protocol into a private-coin finite-message protocol by delegating to Deterministic.FiniteMessage.Protocol.ofProtocol.
The embedding of a binary private-coin protocol into the finite-message framework does not change what the protocol computes. Let \(p\) be a binary private-coin communication protocol with input spaces \(X\) and \(Y\), private-randomness spaces \(\Omega _X\) and \(\Omega _Y\), and output type \(\alpha \), and let \(\widehat{p}\) be the finite-message private-coin protocol obtained by embedding \(p\) (interpreting each Boolean message as an element of a two-element message alphabet). Then for every pair of inputs \(x \in X\), \(y \in Y\) and every pair of private coins \(\omega _x \in \Omega _X\), \(\omega _y \in \Omega _Y\), the randomized execution of \(\widehat{p}\) agrees with that of \(p\):
Let \(p\) be a binary private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \). Then the private-coin finite-message protocol obtained by embedding \(p\) has the same communication complexity as \(p\); that is, viewing each Boolean message of \(p\) as an element of the two-element message alphabet leaves the worst-case number of bits exchanged unchanged.
Let \(p\) be a binary private-coin protocol with randomness spaces \(\Omega _X\) and \(\Omega _Y\), input spaces \(X\) and \(Y\), and output type \(\alpha \), in which Alice’s and Bob’s messages are single bits. Then there exists a private-coin finite-message protocol \(P\) over the same spaces such that, for every pair of inputs \(x \in X\), \(y \in Y\) and every pair of private coins \(\omega _x \in \Omega _X\), \(\omega _y \in \Omega _Y\), the two protocols return the same output when run on \(x, y\) with coins \(\omega _x, \omega _y\), and moreover \(P\) has exactly the same communication complexity as \(p\).