AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PublicCoin.newman

theoremverifiedformalizationimported Lean

Newman's theorem for communication complexity. Let $X$ and $Y$ be finite types, let $f : X \to Y \to \alpha$, and let $\varepsilon, \varepsilon', c \in \bbr$ satisfy $1 < c$ and $c\varepsilon < \varepsilon'$. Then the private-coin communication complexity of $f$ at error tolerance $\varepsilon'$ does not exceed the public-coin communication complexity of $f$ at error tolerance $\varepsilon$ increased by $\lceil \log_2 t(X, Y, \varepsilon, c)\rceil$, where $t(X, Y, \varepsilon, c)$ is the derandomization sample count; that is, \[ \mathrm{CC}^{\mathrm{priv}}_{\varepsilon'}(f) \;\le\; \mathrm{CC}^{\mathrm{pub}}_{\varepsilon}(f) \;+\; \bigl\lceil \log_2 t(X, Y, \varepsilon, c) \bigr\rceil , \] with both complexities taken as values in $\bbn \cup \{\infty\}$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
theorem CommunicationComplexity.PublicCoin.newman
    {X Y α : Type*} [Fintype X] [Fintype Y]
    (f : X → Y → α) (ε ε' : ℝ) (c : ℝ)
    (hc : 1 < c)
    (hε' : c * ε < ε') :
    PrivateCoin.communicationComplexity f ε' ≤
      PublicCoin.communicationComplexity f ε +
        Nat.clog 2
          (FiniteMessage.Protocol.derandomizationSamples
            X Y ε c)
Formalizes
Newman's theorem for communication complexity, as formalized in TCSlib (`CommunicationComplexity.PublicCoin.newman`)
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 63

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
/-- Newman's theorem: for every `c > 1` and every `ε' > c · ε`, the private-coin communication complexity of `f` at error `ε'` is at most the public-coin communication complexity of `f` at error `ε` plus `⌈log₂ (derandomizationSamples X Y ε c)⌉`, i.e. plus `O(log log(|X|·|Y|) + log(1/((c−1) ε)))` bits (the logarithm of `t = O(log(|X|·|Y|)/((c−1)² ε²))` seeds). [RY20, Thm 3.5] / [Rou16, Thm 4.9]; historically [New91]. Deviation: the bound is stated as `R^priv_{ε'}(f) ≤ R^pub_ε(f) + ⌈log₂ derandomizationSamples⌉` for any `ε' > c · ε` with `c > 1`, over arbitrary finite input types `X`, `Y`, in place of the textbook `c + log(n/ε²) + O(1)` at error `2ε`; the slack factor `c > 1` is the Chernoff/union-bound slack of the derandomization (`exists_good_randomness`; the textbook fixes `c = 2`, hence its error `2ε`), and the strict inequality `c · ε < ε'` is what the discretisation of private randomness (`PrivateCoin.communicationComplexity_le_of_finiteMessage`) needs. **Proof sketch.** Step 1: if the public-coin complexity is infinite there is nothing to prove; otherwise it equals some `n`, and there is a public-coin protocol `p` that ε-computes `f` with complexity at most `n`. Step 2: lift `p` to a finite-message public-coin protocol `pfm` with the same runs, hence still ε-computing `f`. Step 3: the Newman protocol `q` built from `pfm` is a private-coin finite-message protocol that `(c · ε)`-computes `f` (`newmanProtocol_ApproxComputes`); since `c · ε < ε'`, the private-coin complexity at error `ε'` is at most the complexity of `q`. Step 4: the complexity of `q` is `⌈log₂ t⌉` plus the complexity of `pfm`, which equals that of `p` and is at most `n`; assemble the chain of inequalities. -/
theorem CommunicationComplexity.PublicCoin.newman
    {X Y α : Type*} [Fintype X] [Fintype Y]
    (f : X → Y → α) (ε ε' : ℝ) (c : ℝ)
    (hc : 1 < c)
    (hε' : c * ε < ε') :
    PrivateCoin.communicationComplexity f ε' ≤
      PublicCoin.communicationComplexity f ε +
        Nat.clog 2
          (FiniteMessage.Protocol.derandomizationSamples
            X Y ε c) := by
  -- Step 1: match on the public-coin complexity
  match h : PublicCoin.communicationComplexity f ε with
  | ⊤ => simp
  | (n : ℕ) =>
    -- There exists a public-coin protocol with complexity ≤ n
    obtain ⟨m, p, hp, hc_le⟩ :=
      (PublicCoin.communicationComplexity_le_iff f ε n).mp (le_of_eq h)
    -- Step 2: lift to FiniteMessage
    let pfm := PublicCoin.FiniteMessage.Protocol.ofProtocol p
    have hpfm_approx : pfm.ApproxComputes f ε := by
      intro x y
      simp only [pfm, PublicCoin.FiniteMessage.Protocol.rrun,
        Deterministic.FiniteMessage.Protocol.ofProtocol_run]
      exact hp x y
    -- Step 3: apply newmanProtocol: get a private-coin FM protocol that (c*ε)-computes f
    let q := pfm.newmanProtocol f ε c hc hpfm_approx
    have hq_approx :=
      FiniteMessage.Protocol.newmanProtocol_ApproxComputes
        pfm f ε c hc hpfm_approx
    -- q (c*ε)-computes f with c*ε < ε', so we can use
    -- communicationComplexity_le_of_finiteMessage
    have hbound :=
      PrivateCoin.communicationComplexity_le_of_finiteMessage
        f ε' (c * ε) hε' q hq_approx
    -- Step 4: bound q.complexity and assemble the chain
    have hpfm_comp : pfm.complexity = p.complexity :=
      Deterministic.FiniteMessage.Protocol.ofProtocol_complexity p
    have hq_comp : q.complexity =
        Nat.clog 2 (FiniteMessage.Protocol.derandomizationSamples X Y ε c) +
          pfm.complexity :=
      FiniteMessage.Protocol.newmanProtocol_complexity pfm f ε c hc hpfm_approx
    set t_log := Nat.clog 2
      (FiniteMessage.Protocol.derandomizationSamples X Y ε c)
    -- Goal is: CC ≤ ↑n + ↑t_log
    calc PrivateCoin.communicationComplexity f ε'
        ≤ (q.complexity : ENat) := hbound
      _ = ↑(t_log + pfm.complexity) := by exact_mod_cast hq_comp
      _ = ↑(t_log + p.complexity) := by rw [hpfm_comp]
      _ ≤ ↑(t_log + n) := by exact_mod_cast Nat.add_le_add_left hc_le _
      _ = ↑n + ↑t_log := by push_cast; ring
See it in the graphDiscuss this resultChallenge it