Lower Bounds in Differentially Private Sublinear-time Algorithms

Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Yet, research has so far concentrated on one or the other. The existence of private algorithms and, separately, sublinear algorithms for many problems poses the question of differential privacy and sublinear time can be combined. Little is known so far, especially when it comes to hardness results on these algorithms. In this paper, we initiate the study of lower bounds for differentially private, sublinear time algorithms. Our main result is the incompatibility of both in the general case. In particular, we prove that a simple problem based on one-way marginals yiels both, a differentially private algorithm and a sublinear time algorithm, but a substantially sublinear time, differentially private algorithm does not exist.