  Differential privacy and sublinear algorithms are both rapidly emerging
algorithmic themes in times of big data analysis. Although recent works have
shown the existence of differentially private sublinear algorithms for many
problems including graph parameter estimation and clustering, little is known
regarding hardness results on these algorithms. In this paper, we initiate the
study of lower bounds for problems that aim for both differentially-private and
sublinear-time algorithms. Our main result is the incompatibility of both the
desiderata in the general case. In particular, we prove that a simple problem
based on one-way marginals yields both a differentially-private algorithm, as
well as a sublinear-time algorithm, but does not admit a ``strictly''
sublinear-time algorithm that is also differentially private.
