65 Communication Complexity — Private Coin Composition
65.1 Overview
This module develops composition operations for private-coin communication protocols with finite message sets. Starting from their deterministic counterparts, it lifts CommunicationComplexity.Deterministic.FiniteMessage.Protocol.map, CommunicationComplexity.Deterministic.FiniteMessage.Protocol.bind, CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.comapRandomness, CommunicationComplexity.Deterministic.FiniteMessage.Protocol.prod, CommunicationComplexity.Deterministic.FiniteMessage.Protocol.pi, CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rbind, and prodDet to the private-coin setting, together with the corresponding simulation lemmas (rrun) and complexity-preservation theorems.
65.2 Declarations
Given a function \(g : \alpha \to \beta \) and a private-coin protocol \(p\) over randomness spaces \(\Omega _X, \Omega _Y\) with output type \(\alpha \), map \(g\) \(p\) is the protocol that runs \(p\) and then applies \(g\) to its output, yielding a protocol with output type \(\beta \) and the same communication tree.
For any inputs \(x : X\), \(y : Y\) and random coins \(\omega _x : \Omega _X\), \(\omega _y : \Omega _Y\), the randomised run of the mapped protocol satisfies
Mapping a function over the output of a protocol does not change its communication complexity: \((p.\mathrm{map}\; g).\mathrm{complexity} = p.\mathrm{complexity}\).
Given a protocol \(p\) with output type \(\alpha \) and a family \(q : \alpha \to \mathrm{Protocol}\; \Omega _X\; \Omega _Y\; X\; Y\; \beta \), CommunicationComplexity.Deterministic.FiniteMessage.Protocol.bind \(p\) \(q\) is the protocol that runs \(p\), observes its output \(a\), and then executes \(q\, a\) on the same inputs using the same randomness spaces.
For all \(x, y, \omega _x, \omega _y\), the randomised run of the bound protocol satisfies
Given functions \(hX : \Omega _X' \to \Omega _X\) and \(hY : \Omega _Y' \to \Omega _Y\), CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.comapRandomness \(hX\) \(hY\) \(p\) reindexes the randomness spaces of \(p\), yielding a protocol over \(\Omega _X'\) and \(\Omega _Y'\) that maps coins through \(hX\) and \(hY\) before passing them to \(p\).
For all \(x, y, \omega _x' : \Omega _X', \omega _y' : \Omega _Y'\),
Reindexing the randomness spaces of a protocol does not change its communication complexity: \((\mathrm{comapRandomness}\; hX\; hY\; p).\mathrm{complexity} = p.\mathrm{complexity}\).
Given protocols \(p_1\) and \(p_2\) with potentially distinct randomness spaces \((\Omega _{X_1}, \Omega _{Y_1})\) and \((\Omega _{X_2}, \Omega _{Y_2})\), CommunicationComplexity.Deterministic.FiniteMessage.Protocol.prod \(p_1\) \(p_2\) runs them in parallel on the same inputs using independent randomness drawn from \(\Omega _{X_1} \times \Omega _{X_2}\) and \(\Omega _{Y_1} \times \Omega _{Y_2}\), returning the pair of their outputs in \(\alpha _1 \times \alpha _2\).
For all \(x, y, \omega _x : \Omega _{X_1} \times \Omega _{X_2}, \omega _y : \Omega _{Y_1} \times \Omega _{Y_2}\),
The communication complexity of the product protocol is the sum of the individual complexities: \((\mathrm{prod}\; p_1\; p_2).\mathrm{complexity} = p_1.\mathrm{complexity} + p_2.\mathrm{complexity}\).
Given a family of protocols \(p : (i : \mathrm{Fin}\, k) \to \mathrm{Protocol}\; (\Omega _{Xf}\, i)\; (\Omega _{Yf}\, i)\; X\; Y\; (\alpha _f\, i)\) with heterogeneous randomness and output types, pi \(p\) runs all \(k\) protocols in parallel on the same inputs using independent randomness from the product spaces \((\prod _i \Omega _{Xf}\, i,\, \prod _i \Omega _{Yf}\, i)\), returning the tuple of outputs \((i : \mathrm{Fin}\, k) \to \alpha _f\, i\).
For all \(x, y, \omega _x, \omega _y\),
The communication complexity of the \(k\)-fold product equals the sum of individual complexities: \((\mathrm{pi}\; p).\mathrm{complexity} = \sum _{i} (p\, i).\mathrm{complexity}\).
Given a protocol \(p\) over randomness \((\Omega _X, \Omega _Y)\) and a family \(q : \alpha \to \mathrm{Protocol}\; \Omega _X'\; \Omega _Y'\; X\; Y\; \beta \), CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.rbind \(p\) \(q\) runs \(p\) with the first component of the coin pair, obtains its output \(a\), then runs \(q\, a\) using a fresh, independent second component, yielding a protocol over \((\Omega _X \times \Omega _X', \Omega _Y \times \Omega _Y')\).
For all \(x, y, \omega _x : \Omega _X \times \Omega _X', \omega _y : \Omega _Y \times \Omega _Y'\),
If the continuation \(q\, a\) has the same complexity \(c\) for every output \(a\) of \(p\), then
Given a private-coin protocol \(p_1\) and a deterministic protocol \(p_2\), CommunicationComplexity.PrivateCoin.FiniteMessage.Protocol.prodDet \(p_1\) \(p_2\) runs both on the same inputs and pairs their outputs in \(\alpha _1 \times \alpha _2\), with \(p_2\) contributing no additional randomness.
For all \(x, y, \omega _x, \omega _y\),
The communication complexity of prodDet \(p_1\) \(p_2\) equals the sum of both complexities: \((\mathrm{prodDet}\; p_1\; p_2).\mathrm{complexity} = p_1.\mathrm{complexity} + p_2.\mathrm{complexity}\).