The Noisy-mean procedure satisfies \(\rho \) -TV-stability and has accuracy \(\alpha ^2 \le O{\frac{d}{(\rho n)^2}}\) 

[Proof of claim:meancomputationnoisyupperbound]
Since the difference in means of two datasets, in norm, is at most \(\frac{2}{n}\) , the outputs are two multivariate Gaussians with variance \(\sigma ^2\)  and means separated by \(\frac{2}{n}\) . From [1]}, the total variation distance between such Gaussian sis at most \(O{\frac{1}{n\sigma }} = \rho \) . For the accuracy, we have \(\alpha ^2 = {{\mu (S) + \xi - \mu (S)}^2} = {{\xi }^2} = d \sigma ^2 = O{\frac{d}{n^2\rho ^2}}\) .
