53 Communication Complexity — Transcript
53.1 Overview
This module develops the theory of syntactic transcripts for deterministic two-party protocols. A transcript records the complete Boolean message sequence produced by a fixed execution path of a protocol; the module establishes that every transcript’s input set is a combinatorial rectangle, that executing the protocol on a pair \((x,y)\) yields a unique transcript, and that the number of distinct transcripts is at most \(2^{\mathrm{complexity}(p)}\). It also provides the swap and comap transport operations on transcripts, both shown to be injective.
53.2 Declarations
For a deterministic protocol \(p\) over input types \(X\) and \(Y\) with output type \(\alpha \), the type \(\mathrm{Transcript}(p)\) records the full message sequence of an execution path: a terminal protocol has a single transcript (unit), while a communication node contributes one Boolean bit together with the transcript of the chosen child protocol.
Given a syntactic transcript \(t\) of a protocol \(p\), Transcript.output \(t\) returns the output value \(\alpha \) attached to the leaf of the execution path described by \(t\).
For a syntactic transcript \(t\) of \(p\), the input set \(\mathrm{inputSet}(t) \subseteq X \times Y\) is the set of all input pairs \((x, y)\) whose execution of \(p\) follows exactly the path described by \(t\). It is defined recursively: for a terminal protocol it is \(X \times Y\), and for a communication node it is the subset of pairs where the current player’s Boolean function matches the bit recorded in \(t\) and the remaining pair belongs to the child transcript’s input set.
For every protocol \(p\) and every syntactic transcript \(t\) of \(p\), the input set \(\mathrm{inputSet}(t)\) is a combinatorial rectangle, i.e. there exist sets \(A \subseteq X\) and \(B \subseteq Y\) such that \(\mathrm{inputSet}(t) = A \times B\).
Given a protocol \(p\) and an input pair \(xy \in X \times Y\), Protocol.transcript \(p\) \(xy\) executes \(p\) on \(xy\) and returns the syntactic transcript reached, recording each Boolean message sent along the way.
For every protocol \(p\) and every input pair \(xy\), the pair \(xy\) belongs to the input set of its own computed transcript: \(xy \in \mathrm{inputSet}(p.\mathrm{transcript}(xy))\).
If an input pair \(xy\) belongs to the input set of a syntactic transcript \(t\) of \(p\), then \(t\) is exactly the transcript computed by running \(p\) on \(xy\): \(p.\mathrm{transcript}(xy) = t\).
For every protocol \(p\) and input pair \(xy\), running \(p\) yields the same result as reading the output from the computed transcript: \(p.\mathrm{run}(xy.1, xy.2) = \mathrm{Transcript.output}(p.\mathrm{transcript}(xy))\).
If two input pairs \(xy\) and \(xy'\) produce the same syntactic transcript under \(p\), then they also produce the same protocol output: \(p.\mathrm{transcript}(xy) = p.\mathrm{transcript}(xy')\) implies \(p.\mathrm{run}(xy.1, xy.2) = p.\mathrm{run}(xy'.1, xy'.2)\).
For natural numbers \(a, b, c_a, c_b\) with \(a \le 2^{c_a}\) and \(b \le 2^{c_b}\), one has \(a + b \le 2^{1 + \max (c_a, c_b)}\).
A deterministic protocol \(p\) has at most \(2^{\mathrm{complexity}(p)}\) syntactic transcripts: \(|\mathrm{Transcript}(p)| \le 2^{p.\mathrm{complexity}}\).
Given a syntactic transcript \(t\) of \(p\), transcriptSwap \(t\) is the corresponding transcript of the swapped protocol \(p.\mathrm{swap}\) (where Alice and Bob exchange roles), obtained by preserving the Boolean message sequence while reinterpreting each node as the opposite player.
For every protocol \(p\), the map transcriptSwap from \(\mathrm{Transcript}(p)\) to \(\mathrm{Transcript}(p.\mathrm{swap})\) is injective: distinct transcripts of \(p\) give distinct transcripts of the swapped protocol.
For every protocol \(p\) and inputs \(x \in X\), \(y \in Y\), swapping the transcript of \(p\) on \((x, y)\) equals the transcript of the swapped protocol on the reversed pair \((y, x)\): \(\mathrm{transcriptSwap}(p.\mathrm{transcript}(x, y)) = p.\mathrm{swap}.\mathrm{transcript}(y, x)\).
Given maps \(f_X : X' \to X\) and \(f_Y : Y' \to Y\) and a syntactic transcript \(t\) of \(p\), transcriptComap \(p\) \(f_X\) \(f_Y\) \(t\) is the corresponding transcript of the pulled-back protocol \(p.\mathrm{comap}(f_X, f_Y)\), obtained by preserving the Boolean message sequence while re-routing through the input maps.
For every protocol \(p\) and input maps \(f_X : X' \to X\), \(f_Y : Y' \to Y\), the map CommunicationComplexity.Deterministic.Protocol.transcriptComap \(p\) \(f_X\) \(f_Y\) from \(\mathrm{Transcript}(p)\) to \(\mathrm{Transcript}(p.\mathrm{comap}(f_X, f_Y))\) is injective.
For every protocol \(p\), maps \(f_X : X' \to X\), \(f_Y : Y' \to Y\), and inputs \(x' \in X'\), \(y' \in Y'\), pulling back the transcript of \(p\) on \((f_X(x'), f_Y(y'))\) equals the transcript of the comapped protocol on \((x', y')\): \(\mathrm{transcriptComap}(p,f_X,f_Y,p.\mathrm{transcript}(f_X(x'),f_Y(y'))) = (p.\mathrm{comap}(f_X,f_Y)).\mathrm{transcript}(x',y')\).