Theorem 3.10 — the Net mechanism is (α, δ)-useful once α ≥ O((VCDIM(C) log|X| log(1/α) + log(1/δ))/(εα²n))

There is an absolute constant $c>0$ with the following property. Let $X$ be a finite data universe, $C$ a class of predicates $\varphi:X\to\{0,1\}$ of VC-dimension $d\ge1$, $n\ge1$ the input size, $\varepsilon>0$, $0<\delta\le1$ and $0<\alpha\le\tfrac12$. If

then a minimum $\tfrac\alpha2$-net $N$ for the counting queries of $C$ exists, and the Net mechanism with privacy parameter $\varepsilon$ run on any such $N$ is $(\alpha,\delta)$-useful for $C$: for every input $z\in X^n$, with probability at least $1-\delta$ its output $\hat D$ satisfies $|Q_\varphi(\hat D)-Q_\varphi(z)|\le\alpha$ for every $\varphi\in C$.

This is the paper's main utility theorem: ignoring computation, any class of counting queries of polynomial VC-dimension over a discretized universe admits a differentially private (Property 3.3) synthetic-database release whose error decays with the database size $n$.

Formalization Note The paper writes $\alpha\ge O(\cdot)$; the $O(\cdot)$ is an absolute constant $c$ quantified before every other binder. The paper obtains $(\alpha,\delta)$ from Corollary 3.5's $(2\alpha',\delta)$ at $\alpha'=\alpha/2$, so the mechanism runs on a minimum $\alpha/2$-net and the factor $2$ is absorbed into $c$. The hypotheses $d\ge1$, $\alpha\le\tfrac12$ (so $\log(1/\alpha)>0$) are disclosed exclusions. Privacy is Property 3.3 and is not restated. Neighbours differ in exactly one entry; logarithms are natural.