Optimal Error of Query Sets Under the Differentially-Private Matrix Mechanism
A common goal of privacy research is to release synthetic data that satisfies a formal privacy guarantee and can be used by an analyst in place of the original data. To achieve reasonable accuracy, a synthetic data set must be tuned to support a specified set of queries accurately, sacrificing fidelity for other queries. This paper considers methods for producing synthetic data under differential privacy and investigates what makes a set of queries "Easy" or "Hard" to answer. The authors consider answering sets of linear counting queries using the matrix mechanism, a recent differentially-private mechanism that can reduce error by adding complex correlated noise adapted to a specified workload.