Abstract
A counting query on a database returns the number of rows of the database that satisfy a given predicate. Despite being one of the simplest classes of aggregate database queries, they are a workhorse of statistical analysis. They capture many natural queries of practical interest, like marginal and range queries, and are a very useful primitive in building more complicated analyses. Counting queries can be further generalized to linear queries, which allow for weighted counting.
In this tutorial, we will cover algorithmic techniques for answering linear queries under the constraints of differential privacy. We will start with basic noise-adding mechanisms. Then we will explain ways to adapt the noise to a desired query workload, both in instance independent ways, using tools from optimization and geometry, and in instance-dependent ways, using algorithms that learn the database as they answer the queries. The tutorial will cover theoretical tools used for answering linear queries and understanding their error properties, as well as empirical results arising in the context of practical use cases.