CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity
For types X, Y, and α, and a function f : X → Y → α, the zero-error private-coin expected communication complexity is defined as the infimum (sInf) in ℝ of the set of all real numbers r such that there exist natural numbers nX and nY and a protocol p : PrivateCoin.Protocol (CoinTape nX) (CoinTape nY) X Y α satisfying p.ApproxComputes f 0 and for all x : X and y : Y, the integral over ω : CoinTape nX × CoinTape nY with respect to volume of p.length (ω.1, x) (ω.2, y) cast to ℝ is at most r.
Statement
open MeasureTheory in noncomputable def CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity {X Y α : Type*} (f : X → Y → α) : ℝ
- Defined in
- arXiv:2611.11488 Section 5.2
- Verified
- 10 Nov 2026
- Axioms
- none listed
- Built on 5
- 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.coinTapeMeasureThe uniform probability measure on
CoinTape n. Every outcome ofnindependent fair coin flips is equally likely. - CommunicationComplexity.PrivateCoin.Protocol.ApproxComputesA private-coin protocol $p$ $\varepsilon$-computes a function $f : X \to Y \to \alpha$ if for every input pair $(x, y)$,…
- CommunicationComplexity.CoinTape$\texttt{CoinTape}(n)$ is the type $\mathrm{Fin}\,n \to \mathrm{Bool}$, i.e.\ the set of all binary strings of length $n$, representing…
- CommunicationComplexity.PrivateCoin.ProtocolA private-coin protocol with randomness spaces $\Omega_X$ and $\Omega_Y$, input spaces $X$ and $Y$, and output type $\alpha$ is…
Read back from the Lean
Given types X, Y, and α, and a function f : X → Y → α, CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity f is defined as the infimum (sInf) of the set of all real numbers r : ℝ such that there exist natural numbers nX and nY and a protocol p : PrivateCoin.Protocol (CoinTape nX) (CoinTape nY) X Y α satisfying:
1. p.ApproxComputes f 0 (the protocol p computes f with error bound 0), and
2. for all x : X and y : Y, the integral over ω : CoinTape nX × CoinTape nY (with respect to the default volume measure) of the protocol execution length (p.length (ω.1, x) (ω.2, y) : ℝ) is less than or equal to r.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
open MeasureTheory in /-- Zero-error private-coin expected communication complexity. -/ noncomputable def CommunicationComplexity.PrivateCoin.zeroErrorCommunicationComplexity {X Y α : Type*} (f : X → Y → α) : ℝ := sInf { r : ℝ | ∃ (nX nY : ℕ) (p : PrivateCoin.Protocol (CoinTape nX) (CoinTape nY) X Y α), p.ApproxComputes f 0 ∧ ∀ (x : X) (y : Y), (∫ (ω : CoinTape nX × CoinTape nY), (p.length (ω.1, x) (ω.2, y) : ℝ)) ≤ r }