On Differentially Private Frequent Itemset Mining.

We consider differentially private frequent itemset mining. We begin by exploring the theoretical difficulty of simultaneously providing good utility and good privacy in this task. While our analysis proves that in general this is very difficult, it leaves a glimmer of hope in that our proof of difficulty relies on the existence of long transactions (that is, transactions containing many items).

On Optimal Differentially Private Mechanisms for Count-Range Queries.

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 θ and θ?" 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.