Return to Colloquia & Seminar listing
Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
Joint Math/CS Theory| Speaker: | Xin Lyu, UC Berkeley |
| Related Webpage: | https://people.eecs.berkeley.edu/~xinlyu/ |
| Location: | 1131 Kemper |
| Start time: | Mon, May 4 2026, 1:10PM |
Description
We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and 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.
Central to our proof is a multi-player communication game, which 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 strong lower bounds on this communication game, scaling polynomially with the number of over-active users. This combined with a novel reduction from the fingerprinting lemma establishes our main results.
This is based on a joint work with Alessandro Epasto and Pasin Manuransgi at Google Research. The preprint is available at arXiv:2602.12209