AFTD Auto-Formalizing Theoretical Domains

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.
Verified
07 Oct 2026
Axioms
none listed
Used by 68

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 α
See it in the graphDiscuss this resultChallenge it