Profile Reconstruction from Private Sketches

Hao Wu, Rasmus Pagh

Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t=0,1,\dots ,n$, the fraction $\vec{f}[t]$ of items in $\mathca…