An Improved Private Mechanism for Small Databases

Aleksandar Nikolov

We study the problem of answering a workload of linear queries $\mathcal{Q}$, on a database of size at most $n=o(|\mathcal{Q}|)$ drawn from a universe $\mathcal{U}$ under the con…