Theorem 7 (Exact symmetric sampling) — AC samples exactly, constructed in polynomial time
OpenSamplingAC0.Supplement.theorem_7There are absolute constants and an algorithm , mapping binary strings to binary strings in deterministic polynomial time, with the following property. For every and every symmetric function , given by its values on the Hamming weights, is the description of an AC sampler with
- at most wires,
- depth at most , and
- output distribution exactly : for uniform on , the string has the same distribution as 's output.
The constants and the algorithm do not depend on or .
Earlier AC samplers for , for instance with the majority function, had an exponentially small error; this sampler has none.
Formalization Note An AC sampler has one circuit of unbounded fan-in AND/OR gates per output bit, and its number of input bits is free. "Constructed efficiently" is computability of (description of ) by a polynomial-time Turing machine on binary strings. For the outputs are literals or constants, which need no wires, so the bound is meaningful for every .
Differences from the source:
- encoding: one AC circuit with outputs → one circuit per output bit, wires summed and depth maximised; reason: a shared circuit with wires gives per-output circuits with at most wires and the same depth, and conversely, so bounds and mean the same
- encoding: "constructed efficiently given the values" → a polynomial-time function on binary strings mapping the value table to the sampler's description (unary indices); reason: the description is injective and polynomially equivalent to a binary-index description for polynomial-size circuits
import Mathlib import Definitions.Def_DDNNFNeg_Supplement_PolyTimeFun import Definitions.Def_SamplingAC0_Supplement_ACSampler import Definitions.Def_SamplingAC0_Supplement_symTarget import Definitions.Def_SamplingAC0_Supplement_encodeSampler set_option autoImplicit false
namespace SamplingAC0.Supplement
/-- **Theorem 7 (Exact symmetric sampling).** Riazanov–Viola, *Sampling Tools and the Power of
AC0*, STOC 2027 submission (manuscript sha256 99c33d30…), Theorem 7, p.4 (proof §4, pp.13–14):
"For every symmetric function f : {0, 1}^n → {0, 1}, there is an AC0 circuit of n^c wires and depth
c whose output distribution is exactly (U, f(U)). The circuit can be constructed efficiently given
the n + 1 values of f on the possible Hamming weights."
**Formalization Note.**
* c-notation (p.2): `c₁` (in `n^{c₁}` wires) and `c₂` (depth) are absolute positive constants,
chosen before the construction algorithm `A`, `n` and `f`.
* A symmetric `f` is given by its value table `v : {0,…,n} → {0,1}` (`f x = v(|x|)`), with no
restriction on `v`. "Exactly" is equality of distributions on `{0,1}^{n+1}`, coordinates ordered
`(x₁, …, xₙ, f(x))` (`symTarget`).
* The circuit is an `ACSampler` (one published `MantriCVQ.ACCircuit` per output bit, wires and depth
as defined there; the number `m` of input bits is free).
* "Constructed efficiently": a single function `A` on binary strings, computable in polynomial time
(published `DDNNFNeg.Supplement.PolyTimeFun`, Mathlib's `TM2ComputableInPolyTime`), maps the
table `v` (written `v(0), …, v(n)`) to the code `encodeSampler C` of a circuit `C` with all the
properties above.
* The statement is for every `n`, including `n = 0, 1`, where literal and constant outputs need no
wires. -/
theorem theorem_7 :
∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧
∃ A : List Bool → List Bool, DDNNFNeg.Supplement.PolyTimeFun A ∧
∀ (n : ℕ) (v : Fin (n + 1) → Bool), ∃ C : ACSampler (n + 1),
A (List.ofFn v) = encodeSampler C ∧
(C.wires : ℝ) ≤ (n : ℝ) ^ c₁ ∧ (C.depth : ℝ) ≤ c₂ ∧
C.dist = symTarget n v := by sorry
end SamplingAC0.Supplement