AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples

defimported Lean

Given finite types $X$ and $Y$ and real parameters $\varepsilon, c$, the number of random samples required for derandomization via Chernoff and union bound is \[ t(X, Y, \varepsilon, c) \;=\; \left\lceil \frac{\log(|X|\cdot|Y|)}{2\,(c-1)^2\,\varepsilon^2} \right\rceil_{\!+} + 1, \] where $\lceil\cdot\rceil_{+}$ denotes the natural-number ceiling.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
variable {Ω X Y α : Type*}
  [Fintype X] [Fintype Y] in
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples
    (X Y : Type*) [Fintype X] [Fintype Y]
    (ε c : ℝ) : ℕ
Defined in
TCSlib, `CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples`
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 7

Lean source view module on GitHub

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory ProbabilityTheory in
variable {Ω X Y α : Type*}
  [Fintype X] [Fintype Y] in
/-- The number `t` of seeds sampled in the derandomization step of Newman's theorem, `⌈log(|X|·|Y|) / (2·(c-1)²·ε²)⌉₊ + 1`; it is chosen so that `|X|·|Y| · exp(−2 (c−1)² ε² t) < 1`. [RY20, Thm 3.5 proof] (`t = O(n/ε²)` sample strings) / [Rou16, Thm 4.9 proof]. Deviation: the count is made explicit as `derandomizationSamples X Y ε c` for arbitrary finite input types `X`, `Y` and a slack factor `c > 1` on the error, rather than the textbook `O(n/ε²)`. -/
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples
    (X Y : Type*) [Fintype X] [Fintype Y]
    (ε c : ℝ) : ℕ :=
  ⌈Real.log (Fintype.card X * Fintype.card Y) /
    (2 * (c - 1) ^ 2 * ε ^ 2)⌉₊ + 1
See it in the graphDiscuss this resultChallenge it