AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol

defimported Lean

Given a public-coin finite-message protocol $p$ over a probability space $\Omega$ that $\varepsilon$-computes $f : X \to Y \to \alpha$, and a constant $c > 1$, the Newman protocol is a private-coin finite-message protocol in which Alice draws a random index $i$ from $\mathtt{newmanIndexSpace}\;X\;Y\;\varepsilon\;c$ and sends it to Bob; both players then run the $i$-th seed from a fixed table of good randomness values (obtained via a Chernoff and union-bound argument) through the original public-coin protocol deterministically.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol
    {Ω X Y α : Type*} [FiniteProbabilitySpace Ω]
    [Fintype X] [Fintype Y]
    (p : FiniteMessage.Protocol Ω X Y α)
    (f : X → Y → α) (ε c : ℝ)
    (hc : 1 < c)
    (hp : p.ApproxComputes f ε) :
    PrivateCoin.FiniteMessage.Protocol
      (newmanIndexSpace X Y ε c) Unit X Y α
Defined in
TCSlib, `CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol`
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
none listed
Built on 42
Used by 3

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
/-- The Newman private-coin protocol built from a public-coin protocol `p` that ε-computes `f`: Alice samples a random index `i` from `newmanIndexSpace` (her private randomness; Bob has none) and sends it to Bob, and both then run the deterministic protocol obtained from `p` by fixing its public randomness to the `i`-th seed of a fixed table of good seeds (the table is the witness of `exists_good_randomness`, obtained by a Chernoff + union bound). [RY20, Thm 3.5 proof] (Alice sends the index of one of the `t` good strings). -/
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.newmanProtocol
    {Ω X Y α : Type*} [FiniteProbabilitySpace Ω]
    [Fintype X] [Fintype Y]
    (p : FiniteMessage.Protocol Ω X Y α)
    (f : X → Y → α) (ε c : ℝ)
    (hc : 1 < c)
    (hp : p.ApproxComputes f ε) :
    PrivateCoin.FiniteMessage.Protocol
      (newmanIndexSpace X Y ε c) Unit X Y α :=
  -- Choose good randomness values via Chernoff + union bound
  let ωs := (FiniteMessage.Protocol.exists_good_randomness
    p f ε c hc hp).choose
  -- Alice sends her random index i ∈ newmanIndexSpace to Bob,
  -- then both simulate with ωs(i)
  PrivateCoin.FiniteMessage.Protocol.alice
    (fun _ ω_x => ω_x)
    (fun i => (p.toDeterministic (ωs i)).toPrivateCoin)
See it in the graphDiscuss this resultChallenge it