Output distribution on a uniform input from a finite domain
DefinitionSamplingAC0_Supplement_cellLawcircuit-complexitycomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sampling
Let be a finite nonempty set and a map. The output distribution is the law of when is uniform on :
In Theorem 6, is the set of inputs of cells with values in , and is the distribution sampled by a cell-probe sampler .
Formalization Note The base mission's output distribution covers only bit inputs ; this is the same construction for an arbitrary finite input domain.
Definition code
import Mathlib
set_option autoImplicit false
namespace SamplingAC0.Supplement
/-- **Output distribution on a uniform input over an arbitrary finite domain.** Riazanov–Viola,
*Sampling Tools and the Power of AC0*, STOC 2027 submission (manuscript sha256 99c33d30…),
Notation, p.2 ("U for the uniform distribution (over suitable domain)"), and p.4 (Theorem 6: the
input of `f : [n]^s → {0,1}^n` is a uniform element of `[n]^s`).
`cellLaw f` is the distribution `f(U)` of `f` applied to a uniform element `U` of the finite
nonempty set `σ`. Theorem 6 uses `σ = Fin s → Fin n`, the `s` input cells with values in `[n]`.
**Formalization Note.** The base mission's `SamplingAC0.law` covers only bit inputs `ι → Bool`;
this is the same pushforward for a general finite input domain. -/
noncomputable def cellLaw {σ β : Type} [Fintype σ] [Nonempty σ] (f : σ → β) : PMF β :=
(PMF.uniformOfFintype σ).map f
end SamplingAC0.Supplement
Source
Riazanov–Viola, Sampling Tools and the Power of AC0, STOC 2027 submission (manuscript sha256 99c33d30…), Notation p.2; Theorem 6 p.4