CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexity
For types X, Y, and α, and a function f : X → Y → α, the zero-error public-coin expected communication complexity is defined as the infimum (sInf) in ℝ of the set of all real numbers r such that there exists a natural number n and a protocol p : PublicCoin.Protocol (CoinTape n) X Y α satisfying p.ApproxComputes f 0 and for all x : X and y : Y, the integral over ω : CoinTape n with respect to volume of p.length (ω, x) (ω, y) cast to ℝ is at most r.
Statement
open MeasureTheory in noncomputable def CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexity {X Y α : Type*} (f : X → Y → α) : ℝ
- Defined in
- arXiv:2611.11488 Section 5.2, equation (5.1)
- 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.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.coinTapeMeasureThe uniform probability measure on
CoinTape n. Every outcome ofnindependent fair coin flips is equally likely. - CommunicationComplexity.PublicCoin.Protocol.ApproxComputesA public-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…
Read back from the Lean
The zero-error public-coin communication complexity of a function f : X → Y → α is defined as the real infimum (sInf) of the set of all r : ℝ such that there exists a natural number n and a public-coin protocol p : PublicCoin.Protocol (CoinTape n) X Y α satisfying:
1. p.ApproxComputes f 0 (protocol p computes f with error parameter 0), and
2. For all inputs x : X and y : Y, the Bochner integral (with respect to the default volume measure on CoinTape n) of the execution length (p.length (ω, x) (ω, y) : ℝ) over all random coin tapes ω : CoinTape n is at most 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 public-coin expected communication complexity. -/ noncomputable def CommunicationComplexity.PublicCoin.zeroErrorCommunicationComplexity {X Y α : Type*} (f : X → Y → α) : ℝ := sInf { r : ℝ | ∃ (n : ℕ) (p : PublicCoin.Protocol (CoinTape n) X Y α), p.ApproxComputes f 0 ∧ ∀ (x : X) (y : Y), (∫ (ω : CoinTape n), (p.length (ω, x) (ω, y) : ℝ)) ≤ r }