Documentation

Complexitylib.Algebraic.LowerBound.Cutwidth.Extractor.Strong.Block.Condenser.Extraction.Internal

Shared-seed extraction from full-entropy block witnesses #

Every full-entropy block witness is uniform on its entire tuple space. The retained-seed total-variation comparison then gives the same bound on all joint seed-output tests.

theorem Algebraic.Cutwidth.Extractor.Internal.weightedBlockTest_of_uniform_witness {α : Type u_1} {Seed : Type u_2} {Ω : Type u_3} [Fintype α] [Fintype Seed] [Fintype Ω] [Nonempty Seed] [Nonempty Ω] {t : ℕ} (p : α → ℝ) (E : α → Seed → Fin t → Ω) (probability : IsProbabilityWeight p) (q : Seed → (Fin t → Ω) → ℝ) (witness : ∀ (y : Seed), IsBlockSource (q y) (Fintype.card Ω)) {δ : ℝ} (close : weightDist (weightedSeededOutput p E) (seedFamilyWeight q) ≤ δ) (T : Finset (Seed × (Fin t → Ω))) :
theorem Algebraic.Cutwidth.Extractor.Internal.weightedStrongSeededExtractor_block {α : Type u_1} {Seed : Type u_2} {Ω : Type u_3} [Fintype α] [Fintype Seed] [Fintype Ω] [Nonempty Seed] [Nonempty Ω] {E : α → Seed → Ω} {K : ℕ} {ε : ℝ} (extract : WeightedStrongSeededExtractor E K ε) {t : ℕ} {p : (Fin t → α) → ℝ} (source : IsBlockSource p K) (T : Finset (Seed × (Fin t → Ω))) :
|weightedSeededTestProb p (fun (x : Fin t → α) (y : Seed) (i : Fin t) => E (x i) y) T - uniformSeededTestProb T| ≤ ↑t * ε