AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_complexity

theoremverifiedimported Lean

Communication cost of the Newman protocol. Let $X$ and $Y$ be finite types, let $\Omega$ be a finite probability space, and let $p$ be a public-coin finite-message protocol over $\Omega$ with private inputs in $X$ and $Y$ and outputs in a type $\alpha$. Fix a target function $f : X \to Y \to \alpha$, real parameters $\varepsilon$ and $c$ with $c > 1$, and suppose that $p$ $\varepsilon$-computes $f$. Then the communication complexity of the associated Newman protocol equals \[ \left\lceil \log_2 t(X, Y, \varepsilon, c) \right\rceil + \mathrm{complexity}(p), \] where $t(X, Y, \varepsilon, c)$ is the derandomization sample count and $\mathrm{complexity}(p)$ is the communication complexity of $p$; that is, running the Newman protocol costs exactly the cost of $p$ together with the number of bits Alice needs to name one seed in the table of size $t(X, Y, \varepsilon, c)$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
theorem CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_complexity
    {Ω X Y α : Type*} [FiniteProbabilitySpace Ω]
    [Fintype X] [Fintype Y]
    (p : FiniteMessage.Protocol Ω X Y α)
    (f : X → Y → α) (ε c : ℝ)
    (hc : 1 < c)
    (hp : p.ApproxComputes f ε) :
    (p.newmanProtocol f ε c hc hp).complexity =
      Nat.clog 2 (FiniteMessage.Protocol.derandomizationSamples
        X Y ε c) + p.complexity
Source
TCSlib, `CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_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
16 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 44
Used by 1

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
/-- The communication complexity of the Newman protocol is `⌈log₂ (derandomizationSamples X Y ε c)⌉ + complexity of p`: Alice's index costs `⌈log₂ t⌉` bits, after which the simulated deterministic protocol costs exactly what `p` costs. [RY20, Thm 3.5 proof]. The proof unfolds the protocol and evaluates the supremum over indices of a constant function. -/
theorem CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol_complexity
    {Ω X Y α : Type*} [FiniteProbabilitySpace Ω]
    [Fintype X] [Fintype Y]
    (p : FiniteMessage.Protocol Ω X Y α)
    (f : X → Y → α) (ε c : ℝ)
    (hc : 1 < c)
    (hp : p.ApproxComputes f ε) :
    (p.newmanProtocol f ε c hc hp).complexity =
      Nat.clog 2 (FiniteMessage.Protocol.derandomizationSamples
        X Y ε c) + p.complexity := by
  unfold newmanProtocol PrivateCoin.FiniteMessage.Protocol.alice
  simp only [Deterministic.FiniteMessage.Protocol.complexity,
    Deterministic.FiniteMessage.Protocol.toPrivateCoin_complexity,
    PublicCoin.FiniteMessage.Protocol.toDeterministic_complexity]
  -- sup of constant function = constant (since newmanIndexSpace is nonempty)
  rw [Finset.sup_const
    (α := ℕ) (Finset.univ_nonempty (α := newmanIndexSpace X Y ε c)),
    show Fintype.card (newmanIndexSpace X Y ε c) =
      FiniteMessage.Protocol.derandomizationSamples X Y ε c
      from Fintype.card_fin _]
See it in the graphDiscuss this resultChallenge it