OpenDP Relations

	A	B	C	D	E	F	G	H
1			Mike Shoemate - Major revisions necessary.
2	Impl	Proof	name	map	metric_in	measure_out	notes	proof
3			Measurements
4	✓		Laplace	d_in / scale	absolute or L1 on floats	pure	eps = d_out	(incomplete) relation proof: https://www.overleaf.com/project/605b5f8a67af815b3757496a
5	✓		Geometric	d_in / scale	absolute or L1 on ints	pure	eps = d_out
6	✓		Gaussian	(d_in / sigma) * sqrt(2 * ln(1.25 / delta)); delta > 0	absolute or L2 on floats	approximate	(eps, del) = d_out, 0 <= eps <= 1, 0 < del
7	PR			d_in^2 / (2 * sigma^2)	absolute or L2 on floats	zCDP	rho = d_out
8	✓		Analytic Gaussian	numerical algorithm	absolute or L2 on floats	approximate
9	PR		Discrete Exponential	d_in / tau	absolute	pure	d_in is finite
10			Base2 Exponential (WIP)		absolute	pure	d_in is finite
11	✓		MT Chain	map_2(map_1(d_in))	*	*
12	PR		seq_comp_static_dist	c	*	pure, approx, zCDP	c = sum_i(d_out_i); assert all_i(meas_i.check(d_in, d_out_i))
13	✓		Stability		L1 or L2	approximate	See https://github.com/opendp/opendp/blob/main/rust/opendp/src/meas/stability.rs
14	✓		Amplify	R(d_in, (eps', del'))	*	pure or approximate	R is the inner measurement being amplified, eps' = ln(1 + p(e^eps - 1)); del' = p * del'; p is the sampling proportion, assuming SRS
15			Cast Measure	R(d_in, (eps, del)), where eps >= xi + rho + sqrt(4 * rho * log(1 / delta))	*	approximate	accepts zCDP measurement in the constructor	from https://arxiv.org/pdf/1605.02065.pdf#page=15
16				R(d_in, (xi, rho)), where rho >= (sqrt(eps - xi + log(1 / delta)) - sqrt(log(1 / delta)))^2	*	zCDP	accepts approximate measurement in the constructor
17				d_out[0] >= d_in && d_out[1] >= 0	*	approximate	accepts pure measurement in the constructor. For composition
18			Smooth Median	d_out >= epsilon	symmetric	pure	The function respects an epsilon provided in the constructor arguments
19
20			Transforms		metric_in	metric_out
21			TT Chain (same as MT)	map_2(map_1(d_in))	*	*
22	✓			R1(d_in, d_mid) && R2(d_mid, d_out)	*	*	d_mid = hint(d_in, d_out)
23	✓		Sum	d_out >= d_in * (U - L) / 2	symmetric	absolute	known n. it takes d_in = 2 to make one (M - m) substitution	old proof: https://github.com/opendp/smartnoise-core/tree/develop/whitepapers/sensitivities/sums
24	✓			d_out >= d_in * max(\|L\|, \|U\|)	symmetric	absolute
25	✓		Count	d_out >= d_in	symmetric	absolute		old proof: https://github.com/opendp/smartnoise-core/tree/develop/whitepapers/sensitivities/counts
26	✓		Count Distinct	d_out >= d_in	symmetric	absolute
27			Count By (Categories)	d_out >= d_in	symmetric	Lp distance, p > 0
28				d_out >= d_in * 2^(1/p - 1)	symmetric	Lp distance, p > 0	known n. Example: L2 distance is p = 2, therefore d_out >= d_in / sqrt(2)	outline/comments: https://github.com/opendp/opendp/issues/158
29	✓		Mean	d_out >= d_in * (U - L) / n / 2	symmetric	absolute	known n. postprocessing the sum	old proof: https://github.com/opendp/smartnoise-core/tree/develop/whitepapers/sensitivities/mean
30			SSxy	d_out >= d_in * (Ux - Lx) * (Uy - Ly) * n / (n + 1) / 2	symmetric	absolute	known n. SSxy = Σ(x_i - X) * (y_i - Y); X = Σx_i / n; Y = Σy_i / n
31			SSx	d_out >= d_in * (U - L)^2 * n / (n + 1) / 2	symmetric	absolute	known n. SSx = Σ(x_i - X)^2; Simplification of SSxy.
32	✓		Covariance	d_out >= d_in * (Ux - Lx) * (Uy - Ly) * n / (n + 1) / 2 / (n - ddof)	symmetric	absolute	known n. postprocessing SSxy	old proof: https://github.com/opendp/smartnoise-core/tree/develop/whitepapers/sensitivities/covariance
33	✓		Variance	d_out >= d_in * (U - L)^2 * n / (n + 1) / 2 / (n - ddof)	symmetric	absolute	known n. postprocessing SSx	old proof: https://github.com/opendp/smartnoise-core/tree/develop/whitepapers/sensitivities/variance
34	OMIT		Quantile	d_out >= d_in * (U - L)	symmetric	absolute	poor utility
35			Raw Moment	d_out >= d_in * (U - L)^k / n / 2	symmetric	absolute	known n. Equal to mean when k = 1
36			Central Moment	d_out >= d_in * (U - L)^k * n / (n + 1) / 2	symmetric	absolute	known n. Equal to variance when k = 2
37	SN		QuantileUtility	d_out >= d_in * max(1 - alpha, alpha)	symmetric	absolute
38	✓		Clamp	d_out >= d_in	symmetric	symmetric		old proof: https://github.com/opendp/smartnoise-core/tree/develop/whitepapers/data_processing
39				d_out >= min(d_in, U - L)	absolute	absolute	If you clamp an aggregated value, the sensitivity is at most the range of the clamp.
40	✓		Impute	d_out >= d_in	symmetric	symmetric	includes impute_constant, impute_uniform_float	old proof: same location as clamp
41	✓		Cast	d_out >= d_in	symmetric	symmetric	includes cast, cast_default, cast_inherent
42			Resize	d_out >= d_in * 2	symmetric	symmetric		old proof: same location as clamp
43			Join	d_out >= 2 * (d_in_l * m + d_in_r * l + 2 * d_in_l * d_in_r)	(symmetric, symmetric)	symmetric	m is left truncation constant, l is right truncation constant
44			Truncate	d_out >= d_in * k	symmetric	symmetric	k is max-user-contribution, saved as domain descriptor
45	SN		Theil-Sen Transform	d_out >= d_in * k	symmetric	symmetric	k is maximum number of matchings a user is involved in
46			Stable Unary	d_out >= d_in	symmetric	symmetric	abs, ln, etc.
47			Stable Binary	d_out >= d_in_l	symmetric	symmetric	add, mul, etc; if d_in_l == d_in_r && both are identically ordered
48	✓		RowTransform	d_out >= d_in	symmetric	symmetric	user defined function, only available in reduced privacy model
49			LoadCSV	d_out >= d_in	symmetric	symmetric	d_in specified in constructor; can be used to choose the execution engine- this component chooses rust
50	CONTRIB		CoinPress Mean
51	CONTRIB		CoinPress Covariance
52			KMeans
53	CONTRIB		Gradient Descent
54			Partition
55	✓		Is Equal	d_out >= d_in	symmetric	symmetric
56	✓		Cast Metric	d_out >= d_in * 2	substitute	symmetric
57	✓			d_out >= d_in / 2	symmetric	substitute	is ceil necessary? should it enforce even-ness on sized domains?
58
59
60
61
62
63
64	PR	In pull request
65	SN	In smartnoise-core
66	OMIT	Doesn't meet utility or design requirements
67	CONTRIB	Prior work available but may not be integrated
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100