2026-07-23T17:26:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22647 2026-04-17T05:31:48Z ddc:004 open_access

Differential Privacy and Sublinear Time Are Incompatible Sometimes Blocki, Jeremiah Fichtenberger, Hendrik Grigorescu, Elena Mukherjee, Tamalika differential privacy sublinear algorithms sublinear-time algorithms one-way marginals lower bounds 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeremiah Blocki and Hendrik Fichtenberger and Elena Grigorescu and Tamalika Mukherjee 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.19 urn:nbn:de:0030-drops-226473 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode