CommunicationComplexity.Deterministic.Protocol
inductiveimported Lean
A deterministic two-party communication protocol over input types $X$ (Alice) and $Y$ (Bob) producing a value of type $\alpha$ is an inductive type with three constructors: an output node carrying the final value, an alice node in which Alice applies a function $f : X \to \mathrm{Bool}$ to her input and branches on the resulting bit, and a bob node in which Bob does the same with a function $g : Y \to \mathrm{Bool}$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in inductive CommunicationComplexity.Deterministic.Protocol (X Y α : Type*)
- Defined in
- TCSlib, `CommunicationComplexity.Deterministic.Protocol`
- Lean proof
- By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.CommunicationComplexity.Deterministic.Protocol← CommunicationComplexity.Deterministic.Protocol (TCSlib/CommunicationComplexity/DeterministicCC/DetBasic.lean:60): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 68
- CommunicationComplexity.Deterministic.communicationComplexity_le_iffThreshold characterization of deterministic communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function and let $n$…
- CommunicationComplexity.Deterministic.Protocol.aux_finiteFiniteness of the auxiliary leaf rectangles. Let $X$, $Y$, and $\alpha$ be types, let $p$ be a deterministic two-party communication…
- CommunicationComplexity.Deterministic.Protocol.leafRectanglesAuxFor a protocol $p$ and sets $A \subseteq X$, $B \subseteq Y$, $\texttt{leafRectanglesAux}(p, A, B)$ is the collection of rectangles…
- CommunicationComplexity.Deterministic.Protocol.aux_isRectangleAuxiliary leaf sets are rectangles. Let $p$ be a deterministic two-party communication protocol over input types $X$ (Alice) and $Y$…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_isMonoPartitionLeaf rectangles of a protocol form a monochromatic partition. Let $p$ be a deterministic two-party communication protocol over input types…
- CommunicationComplexity.Deterministic.Protocol.aux_disjointDistinct auxiliary leaf rectangles are disjoint. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_coverLeaf rectangles cover the input space. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$ (Bob)…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_runEmbedding preserves protocol output. Let $X$ and $Y$ be the input types of Alice and Bob, let $\alpha$ be an output type, and let $p$ be a…
- protocol_leaf_countThe number of leaves of a deterministic communication protocol $p$ is $1$ if $p$ is an output node, and the sum of the leaf counts of both…
- CommunicationComplexity.Deterministic.le_communicationComplexity_iffLower-bound characterization of communication complexity. Let $f : X \to Y \to \alpha$ be a two-argument function, let…
- CommunicationComplexity.Deterministic.Protocol.complexityThe communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice…
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_sum_rectanglesSigned bias as a sum over leaf rectangles. Let $\mu$ be a finite probability space on $X \times Y$, let $p$ be a deterministic Boolean…
- CommunicationComplexity.Deterministic.Protocol.rectangleSign_absRectangle sign has absolute value one. Let $p$ be a deterministic Boolean two-party communication protocol on input types $X$ (Alice) and…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_disjointDistinct leaf rectangles are disjoint. Let $p$ be a deterministic two-party communication protocol over input types $X$ and $Y$ producing…
- CommunicationComplexity.Deterministic.Protocol.aux_monoLeaf rectangles are output-monochromatic. Let $p$ be a deterministic communication protocol over input types $X$ (Alice) and $Y$ (Bob)…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_complexityComplexity of the complete Alice-query tree. Fix a natural number $d$, together with binary query functions…
- CommunicationComplexity.Deterministic.Protocol.rectangleSignFor a deterministic Boolean protocol $p$ and a set $R \subseteq X \times Y$, the rectangle sign is $+1$ if the protocol outputs…
- CommunicationComplexity.Deterministic.Protocol.aux_alice_bitAlice's bit is fixed on a child's leaf rectangle. Let $p$ be a protocol on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$, let…
- CommunicationComplexity.Deterministic.Protocol.mem_leafRectanglesFinsetMembership in the finite set of leaf rectangles. Let $X \times Y$ carry the structure of a finite probability space, let $p$ be a…
- CommunicationComplexity.Deterministic.Protocol.aux_cardLeaf rectangle count bounded by two to the complexity. Let $p$ be a deterministic two-party communication protocol with input types $X$…
- CommunicationComplexity.Deterministic.Protocol.lengthFor a deterministic two-party protocol p and inputs x and y, the transcript length p.length x y is the number of bits communicated by the…
- CommunicationComplexity.PublicCoin.ProtocolA public-coin protocol over shared randomness $\Omega$, with Alice's private input in $X$ and Bob's in $Y$ producing an output in…
- CommunicationComplexity.Deterministic.Protocol.signedBias_eq_one_sub_two_distributionalErrorSigned correlation and distributional error. Let $X$ and $Y$ be the input types of Alice and Bob, and let $\mu$ be a finite probability…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocolA noncomputable function that converts a finite-message protocol $p$ into a binary protocol…
- CommunicationComplexity.Deterministic.Protocol.rectangleSign_eq_boolSignRectangle sign equals Boolean sign on leaf rectangles. Let $p$ be a deterministic two-party communication protocol with Boolean output,…
- CommunicationComplexity.Functions.Equality.le_communicationComplexityDeterministic complexity lower bound for equality. For every natural number $n \ge 1$, the deterministic communication complexity of the…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_runConversion to binary protocol preserves output. Let $p$ be a finite-message deterministic two-party protocol over input types $X$ and $Y$…
- CommunicationComplexity.Deterministic.Protocol.logb_le_complexity_of_distributionalErrorDiscrepancy lower bound on communication complexity. Let $\mu$ be a finite probability space on $X \times Y$, let…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocol_complexityEmbedding binary protocols preserves complexity. Let $p$ be a deterministic binary two-party communication protocol over input types $X$…
- CommunicationComplexity.Deterministic.Protocol.sum_indicator_leafRectangles_eqIndicator sum over leaf rectangles recovers the protocol output. Let $X$ and $Y$ be input types whose product $X \times Y$ carries a…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_existsBinary simulation of a finite-message protocol. Let $X$, $Y$, and $\alpha$ be types, and let $p$ be a finite-message two-party protocol…
- CommunicationComplexity.Deterministic.Protocol.aux_disjoint_alice_of_neLeaf rectangles on opposite Alice branches are disjoint. Let $p, q$ be protocols on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$,…
- CommunicationComplexity.Deterministic.Protocol.one_sub_two_distributionalError_le_two_pow_mulDiscrepancy lower bound on distributional error. Let $\mu$ be a finite probability measure on $X \times Y$, let…
- CommunicationComplexity.Functions.Indexing.le_oneWayCommunicationComplexityOne-way complexity of Index is at least $n$. Every correct deterministic one-way protocol for $\mathrm{IND}_n$ has cost at least $n$; that…
- CommunicationComplexity.Deterministic.Protocol.swapGiven a protocol $p$ over $X \times Y$,
swapproduces a protocol over $Y \times X$ by exchanging the roles of Alice and Bob… - CommunicationComplexity.Deterministic.Protocol.leafRectanglesThe leaf rectangles of a protocol $p : \texttt{Protocol}\,X\,Y\,\alpha$ form the collection…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAliceAn auxiliary construction: given $d$ binary query functions $\mathrm{query}_i : X \to \mathrm{Bool}$ and a family of binary protocols…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.completeTreeAlice_runEvaluation of the complete Alice-query tree. Fix a depth $d \in \bbn$, a family of binary query functions…
- CommunicationComplexity.Deterministic.Protocol.comap_complexityPull-back preserves communication complexity. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from…
- CommunicationComplexity.Deterministic.Protocol.aux_subsetAuxiliary leaf rectangles lie within the constraint. Let $p$ be a deterministic two-party communication protocol over input types $X$…
- CommunicationComplexity.Deterministic.communicationComplexityThe deterministic communication complexity of $f : X \to Y \to \alpha$ is defined as…
- CommunicationComplexity.Deterministic.Protocol.leafRectanglesFinsetGiven a finite probability space $\mu$ on $X \times Y$ and a deterministic protocol $p$, this is the canonical
Finsetenumerating… - CommunicationComplexity.PublicCoin.Protocol.toDeterministicGiven a public-coin protocol $p$ over randomness space $\Omega$ and a fixed outcome $\omega : \Omega$,…
- CommunicationComplexity.Deterministic.foolingSet_ncard_le_pow_of_communicationComplexity_leFooling set bound from communication complexity. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- CommunicationComplexity.Deterministic.Protocol.distributionalErrorGiven a deterministic protocol $p : \mathrm{Protocol}\,X\,Y\,\alpha$, a finite probability space $\mu$ on $X \times Y$, and a target…
- CommunicationComplexity.Deterministic.Protocol.comap_runPull-back commutes with protocol execution. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from $X$…
- CommunicationComplexity.Deterministic.Protocol.ComputesA protocol $p$ computes a two-argument function $f : X \to Y \to \alpha$ if $p.\texttt{run}\,x\,y = f\,x\,y$ for all inputs $x : X$…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.encode_aliceBinary encoding of a finite-alphabet message from Alice. Let $X$, $Y$, and $\alpha$ be types, let $\beta$ be a finite nonempty type, let…
- CommunicationComplexity.Functions.Equality.communicationComplexity_zeroDeterministic complexity of equality at $n = 0$. Let…
- CommunicationComplexity.Deterministic.Protocol.runGiven a protocol $p$,
runevaluates $p$ on inputs $x : X$ and $y : Y$ by recursively following the bit-branching structure until… - CommunicationComplexity.Deterministic.communicationComplexity_le_of_finiteMessage_protocolUpper bound witnessed by a finite-message protocol. Let $f : X \to Y \to \alpha$ and let $p$ be a finite-message protocol over $X$, $Y$,…
- CommunicationComplexity.Deterministic.Protocol.aux_coverLeaf rectangles cover the input rectangle. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from a…
- min_leaf_countGiven types $X$, $Y$, and $\alpha$ and a function $f : X \to Y \to \alpha$, the minimum protocol leaf count $\mathrm{min\_leaf\_count}(f)$…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.ofProtocolEmbeds a binary protocol into the generalized finite-message framework by treating each Boolean message as an element of…
- CommunicationComplexity.Deterministic.Protocol.swap_runRole swap preserves protocol output. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from $X$, Bob's…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_isRectangleLeaf rectangles are combinatorial rectangles. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from…
- CommunicationComplexity.Deterministic.mono_partition_of_communicationComplexity_leLow deterministic complexity yields a small monochromatic partition. Let $g : X \times Y \to \alpha$ be a two-argument function, and let…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_finiteFiniteness of a protocol's leaf rectangles. For any deterministic two-party communication protocol $p$ over input types $X$ (Alice) and…
- CommunicationComplexity.Deterministic.Protocol.comapGiven functions $f_X : X' \to X$ and $f_Y : Y' \to Y$,
comappulls back a protocol $p$ over $X \times Y$ to a protocol over… - CommunicationComplexity.Deterministic.Protocol.aux_bob_bitBob's bit is fixed on a child's leaf rectangle. Let $p$ be a protocol on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$, let…
- CommunicationComplexity.Deterministic.Protocol.aux_disjoint_bob_of_neLeaf rectangles on opposite Bob branches are disjoint. Let $p, q$ be protocols on $X \times Y$, let $A \subseteq X$, $B \subseteq Y$, let…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_cardLeaf rectangle count is at most two to the complexity. Let $p$ be a deterministic two-party communication protocol over input types $X$…
- CommunicationComplexity.Deterministic.Protocol.swap_complexityRole swap preserves communication complexity. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from a…
- CommunicationComplexity.Deterministic.le_communicationComplexity_of_forall_lt_ncardRectangle-partition lower bound on communication complexity. Let $g : X \to Y \to \alpha$ be a two-argument function and let $n$ be a…
- CommunicationComplexity.Deterministic.Protocol.leafRectangles_monoLeaf rectangles of a protocol are monochromatic. Let $p$ be a deterministic two-party communication protocol over input types $X$ and $Y$…
- CommunicationComplexity.PrivateCoin.ProtocolA private-coin protocol with randomness spaces $\Omega_X$ and $\Omega_Y$, input spaces $X$ and $Y$, and output type $\alpha$ is…
- CommunicationComplexity.Deterministic.FiniteMessage.Protocol.toProtocol_complexityConversion to a binary protocol preserves complexity. Let $p$ be a finite-message deterministic two-party communication protocol over…
- CommunicationComplexity.Deterministic.Protocol.swap_swapRole swap is an involution. Let $p$ be a deterministic two-party communication protocol with Alice's inputs drawn from a type $X$, Bob's…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in /-- A deterministic two-party communication protocol where Alice holds input `x : X`, Bob holds input `y : Y`, and the protocol computes a value of type `α`. At each step, either Alice or Bob sends a single bit based on their input, and the protocol branches accordingly. [RY20, Ch. 1, Definition (2-party deterministic protocol)]. The tree is represented inductively: a leaf carries the output value, and an internal node carries its owner's message function together with the two subtrees. -/ inductive CommunicationComplexity.Deterministic.Protocol (X Y α : Type*) where | output (val : α) : Protocol X Y α | alice (f : X → Bool) (P : Bool → Protocol X Y α) : Protocol X Y α | bob (f : Y → Bool) (P : Bool → Protocol X Y α) : Protocol X Y α