Efficient Differentially Private $F_0$ Linear Sketching

Understand

A powerful feature of linear sketches is that from sketches of two data vectors, one can compute the sketch of the difference between the vectors.

• This allows us to answer fine-grained questions about the difference between two data sets.
• In this work, we consider how to construct sketches for weighted $F_0$, i.e., the summed weights of the elements in the data set, that are small, differentially private, and computationally efficient.
• Let a weight vector $w\in(0,1]^u$ be given.