Documentation

CommunicationComplexity.PublicCoin.Derandomization

Derandomization via Chernoff + Union Bound #

Given a public-coin protocol that ε-computes a function f, we show there exist finitely many randomness values ω₁, ..., ωₜ such that for every input (x, y), at most a c·ε fraction of the ωᵢ produce incorrect outputs.

source
noncomputable def CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.derandomizationSamples (X : Type u_5) (Y : Type u_6) [Fintype X] [Fintype Y] (ε c : ℝ) :
ℕ

The number of random samples needed for derandomization via Chernoff + union bound: ⌈log(|X|·|Y|) / (2·(c-1)²·ε²)⌉₊ + 1.

Equations
Instances For
    source
    theorem CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.exists_good_randomness {Ω : Type u_1} {X : Type u_2} {Y : Type u_3} {α : Type u_4} [Fintype X] [Fintype Y] [FiniteProbabilitySpace Ω] (p : Protocol Ω X Y α) (f : X → Y → α) (ε c : ℝ) (hc : 1 < c) (hp : p.ApproxComputes f ε) :
    ∃ (ωs : Fin (derandomizationSamples X Y ε c) → Ω), ∀ (x : X) (y : Y), ↑{i : Fin (derandomizationSamples X Y ε c) | p.rrun x y (ωs i) ≠ f x y}.card / ↑(derandomizationSamples X Y ε c) ≤ c * ε

    Chernoff + union bound derandomization: given a protocol that ε-computes f with c > 1, there exist t = O(log(|X|·|Y|)/((c-1)²ε²)) randomness values such that for every input (x, y), at most a c·ε fraction of them produce incorrect outputs.