Search papers, labs, and topics across Lattice.
This paper establishes the first unconditional space lower bound for user-level differential privacy by introducing a novel multi-player communication game that links the hardness of low-memory private algorithms to the necessity of contribution capping. The authors demonstrate that the communication complexity of winning this game translates directly to memory lower bounds for private algorithms. They apply this framework to distinct element estimation, proving an $\widetilde{\Omega}(T^{1/3})$ space lower bound, and generalize the technique to derive lower bounds for private medians, quantiles, and max-select.
User-level differential privacy demands a surprising amount of memory: even for basic tasks like counting distinct elements, private algorithms provably require significantly more space than their non-private counterparts.
We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and differential privacy is well-understood, the inherent cost of privacy regarding memory use remains largely unexplored. This paper establishes for the first time an unconditional space lower bound for user-level differential privacy by introducing a novel proof technique based on a multi-player communication game. Central to our approach, this game formally links the hardness of low-memory private algorithms to the necessity of ``contribution capping''-- tracking and limiting the users who disproportionately impact the dataset. We demonstrate that winning this communication game requires transmitting information proportional to the number of over-active users, which translates directly to memory lower bounds. We apply this framework, as an example, to the fundamental problem of estimating the number of distinct elements in a stream and we prove that any private algorithm requires almost $\widetilde{\Omega}(T^{1/3})$ space to achieve certain error rates in a promise variant of the problem. This resolves an open problem in the literature (by Jain et al. NeurIPS 2023 and Cummings et al. ICML 2025) and establishes the first exponential separation between the space complexity of private algorithms and their non-private $\widetilde{O}(1)$ counterparts for a natural statistical estimation task. Furthermore, we show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
