Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms

Alessandro Epasto, Xin Lyu, Pasin Manurangsi

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 inheren…