Theorem 1.1 — Characterization of private uniform language generation
ProvedPrivateUniformGen.Characterization.theorem_1_1differential-privacylanguage-generationp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any countable example space and any nonempty, possibly uncountable family of infinite subsets of . Then
Private uniform generatability means there are , algorithms for every , and nonnegative errors with , such that is -private on all of and almost surely returns an infinite subset of excluding the input on every sequence of distinct examples from every . The closure dimension retains its finite value . This is both directions of the paper's main characterization, without restrictions on class cardinality.
Differences from the source:
- reading: measurable subsets of the output range → the product sigma-algebra on subsets of X; randomized algorithms are arbitrary maps to probability laws; reason: membership events generate this sigma-algebra; X is countable, all stated utility events are measurable, and the upper-bound laws have finite support; no computability requirement is imposed by the source
- encoding: randomized algorithms and probability-one guarantees → ProbabilityMeasure-valued maps and almost-everywhere predicates; reason: bundles probability one for every input and expresses the identical almost-sure events without allowing zero measures
- encoding: CDim in {-1,0,1,...,infinity} and nonnegative ranks with infinity → WithTop integers for CDim and extended naturals for ranks and Helly numbers; reason: retains both -1 and infinity; finite-value projections are used only where finiteness is assumed or follows from the source results
- encoding: unrestricted branching trees with equal root-to-leaf node counts → the inductive existence predicate HasTree with unlimited arity; reason: sets of child labels permit arbitrary branching; equal duplicate labels can be merged without altering tree existence or any intersection
Preamble
import Mathlib import Definitions.Def_PrivateUniformGen_Characterization_Languages import Definitions.Def_PrivateUniformGen_Characterization_Branching open MeasureTheory
Formal statement
namespace PrivateUniformGen.Characterization
theorem theorem_1_1 {X : Type} [Countable X] (C : LanguageClass X) :
PrivatelyUniformlyGeneratable C ↔ closureDim C < ⊤ ∧ nbDim C ⊤ < ⊤ := by sorry
end PrivateUniformGen.Characterization
Source
Di Wang, Peng Ye, STOC 2027 submission #178 (October 2026), Theorem 1.1, p. 3. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/178.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.