Theorem 2 (Reducing input length) — a -local map from bits nearly preserves
OpenSamplingAC0.Supplement.theorem_2Let be any function and
the base-2 logarithm of the number of values takes. There are absolute constants such that for all naturals and with
there is a -local map with
Here , are uniform and is statistical distance. The constants do not depend on , , , or ; the map may depend on all of them.
The theorem replaces the input bits of a sampler by bits through a map in which each bit reads only seed bits, so the reduction can be carried out inside AC or NC (Corollary 3 of the paper).
Formalization Note The four occurrences of in the paper's statement are four separate constants, per the paper's -notation. is a real number, compared with , and over the reals. Since both laws are supported on the finite range of , statistical distance is the finite sum over that range, allowing the paper's arbitrary codomain .
Differences from the source:
- encoding: statistical distance between laws on an arbitrary set → the defining finite sum over the range of ; reason: both laws are supported on this finite range, so the sum is exactly the source's statistical distance and no instance is excluded
import Mathlib import Definitions.Def_SamplingAC0_law import Definitions.Def_SamplingAC0_tvDist import Definitions.Def_SamplingAC0_Supplement_IsLocal set_option autoImplicit false
namespace SamplingAC0.Supplement
/-- **Theorem 2 (Reducing input length).** Riazanov–Viola, *Sampling Tools and the Power of AC0*,
STOC 2027 submission (manuscript sha256 99c33d30…), Theorem 2, p.3 (proof §5, pp.14–16):
"Let F be a function from {0, 1}^m to Y, and define ℓ := log₂ |supp(F(U_m))|. Then there exists a
k-local map G from {0, 1}^r to {0, 1}^m such that ∆(F(G(U_r)), F(U_m))² ≤ r^{−ck} +
2^{ℓ−r}(1 + 2^{−ck})^r, for any k and r such that c ≤ k ≤ r^c and ℓ ≤ r ≤ 2ℓ."
**Formalization Note.**
* c-notation (p.2): the four occurrences of `c` are four absolute positive constants `c₁` (in
`r^{−c₁k}`), `c₂` (in `2^{−c₂k}`), `c₃` (in `c₃ ≤ k`) and `c₄` (in `k ≤ r^{c₄}`), chosen before
`m`, `Y`, `F`, `k` and `r`. The map `G` may depend on `F`, `k` and `r`.
* `Y` is arbitrary, as on the page. Since both distributions are supported on the finite range of
`F`, their statistical distance is written as the finite sum over that range; classical equality
is used only to form the range as a `Finset`.
* `supp(F(U_m))` is the range of `F` (the uniform input has full support); `ℓ` is a real number and
`k`, `r` are compared with it, and with `r^{c₄}`, as reals.
* `F(G(U_r))` is `law (F ∘ G)` and `F(U_m)` is `law F`. -/
theorem theorem_2 : open Classical in
∃ c₁ c₂ c₃ c₄ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧ 0 < c₃ ∧ 0 < c₄ ∧
∀ (m : ℕ) (Y : Type) (F : (Fin m → Bool) → Y) (k r : ℕ),
c₃ ≤ (k : ℝ) → (k : ℝ) ≤ (r : ℝ) ^ c₄ →
Real.logb 2 ((Finset.univ.image F).card : ℝ) ≤ (r : ℝ) →
(r : ℝ) ≤ 2 * Real.logb 2 ((Finset.univ.image F).card : ℝ) →
∃ G : (Fin r → Bool) → (Fin m → Bool), IsLocal k G ∧
((1 / 2 : ℝ) * ∑ y ∈ Finset.univ.image F,
|(SamplingAC0.law (F ∘ G) y).toReal - (SamplingAC0.law F y).toReal|) ^ 2 ≤
(r : ℝ) ^ (-(c₁ * k)) +
(2 : ℝ) ^ (Real.logb 2 ((Finset.univ.image F).card : ℝ) - r) *
(1 + (2 : ℝ) ^ (-(c₂ * k))) ^ r := by sorry
end SamplingAC0.Supplement