Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation

Mark Bun, Thomas Steinke

The simplest and most widely applied method for guaranteeing differential privacy is to add instance-independent noise to a statistic of interest that is scaled to its global sensi…