Differentially Private Sparse Vectors with Low Error, Optimal Space, and Fast Access

Martin Aumüller, Christian Janos Lebeda, Rasmus Pagh

Representing a sparse histogram, or more generally a sparse vector, is a fundamental task in differential privacy. An ideal solution would use space close to information-theoretica…