title: On Optimal Differentially Private Mechanisms for Count-Range Queries.
abstract: While there is a large and growing body of literature on differentially private mechanisms for answering various classes of queries, to the best of our knowledge "count-range" queries have not been studied. These are a natural class of queries that ask "is the number of rows in a relation satisfying a given predicate between two integers θ1and θ2?" Such queries can be viewed as a simple form of SQL "having" queries. We begin by developing a provably optimal differentially private mechansim for count-range queries for a single consumer. For count queries (in contrast to count-range queries), Ghosh et al. [9] have provided a differentially private mechanism that simultaneously maximizes utility for multiple consumers. This raises the question of whether such a mechanism exists for count-range queries. We prove that the answer is no - for count range queries, no such mechanism exists. However, perhaps surprisingly, we prove that such a mechanism does exist for "threshold" queries, which are simply count-range queries for which either θ1= 0 or θ2= +∞. Furthermore, we prove that this mechanism is a two-approximation for general count-range queries.
authors.affiliation: University of Wisconsin-Madison, zeng@cs.wisc.edu.
authors.forename: Chen
authors.initials: C
authors.lastname: Zeng
authors.affiliation: University of Wisconsin-Madison, jyc@cs.wisc.edu.
authors.forename: Jin-Yi
authors.initials: JY
authors.lastname: Cai
authors.affiliation: Microsoft Research Asia, pinyanl@microsoft.com.
authors.forename: Pinyan
authors.initials: P
authors.lastname: Lu
authors.affiliation: University of Wisconsin-Madison, naughton@cs.wisc.edu.
authors.forename: Jeffrey F
authors.initials: JF
authors.lastname: Naughton