AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Deterministic.Protocol.complexity

defimported Lean

The communication complexity of a protocol $p$ is the worst-case total number of bits exchanged: an output node costs $0$, while an alice or bob node costs $1$ plus the maximum complexity of the two sub-protocols reached by the bit $\mathtt{false}$ and the bit $\mathtt{true}$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
def CommunicationComplexity.Deterministic.Protocol.complexity : Protocol X Y α → ℕ
Defined in
TCSlib, `CommunicationComplexity.Deterministic.Protocol.complexity`
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 1
Used by 32

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
variable {X Y α : Type*} in
/-- The communication complexity of a protocol, i.e. the worst-case number of bits exchanged, which is the depth of the protocol tree. [RY20, Ch. 1, Definition (computing a function, complexity, rounds)]. -/
def CommunicationComplexity.Deterministic.Protocol.complexity : Protocol X Y α → ℕ
  | .output _ => 0
  | .alice _ P => 1 + max (P false).complexity (P true).complexity
  | .bob _ P => 1 + max (P false).complexity (P true).complexity
See it in the graphDiscuss this resultChallenge it