AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PrivateCoin.communicationComplexity

defimported Lean

The $\varepsilon$-error private-coin randomized communication complexity of $f : X \to Y \to \alpha$ is the extended natural number \[ R_\varepsilon(f) \;=\; \inf_{\substack{n_X, n_Y \in \mathbb{N},\\ p : \mathrm{Protocol}(\{0,1\}^{n_X}, \{0,1\}^{n_Y}, X, Y, \alpha),\\ p.\mathrm{ApproxComputes}\,f\,\varepsilon}} p.\mathrm{complexity}, \] i.e.\ the minimum worst-case number of bits exchanged over all private-coin randomized protocols that compute $f$ with error at most $\varepsilon$ on every input.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
noncomputable def CommunicationComplexity.PrivateCoin.communicationComplexity
    {X Y α} (f : X → Y → α) (ε : ℝ) : ENat
Defined in
TCSlib, `CommunicationComplexity.PrivateCoin.communicationComplexity`
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.
Verified
07 Oct 2026
Axioms
none listed
Built on 22
Used by 4

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
/-- The `ε`-error private-coin randomized communication complexity `R^priv_ε(f)` of `f`, defined as the minimum worst-case number of bits exchanged over all private-coin randomized protocols that compute `f` with error at most `ε` on every input [RY20, Ch. 3, §Variants of Randomized Protocols]. Deviation: the minimum is an infimum in `ℕ∞` (equal to `⊤` if no protocol qualifies), and the two players' private randomness are coin tapes `CoinTape nX` and `CoinTape nY` of some finite lengths, quantified over all `nX`, `nY`. -/
noncomputable def CommunicationComplexity.PrivateCoin.communicationComplexity
    {X Y α} (f : X → Y → α) (ε : ℝ) : ENat :=
  ⨅ (nX : ℕ) (nY : ℕ)
    (p : Protocol (CoinTape nX) (CoinTape nY) X Y α)
    (_ : p.ApproxComputes f ε),
    (p.complexity : ENat)
See it in the graphDiscuss this resultChallenge it