Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

Lun Wang, Iosif Pinelis, Dawn Song

We prove that ${\mathbb{F}}_p$ sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when $p\in (0,1]$. ${\mathbb{F}}_p$ sketc…