Aaron Roth

In this thesis, we consider the problem of how one should perform computations on private data. We specifically consider algorithms which preserve the recent formalization of privacy known as differential privacy. The fundamental tradeoff that we consider is that of privacy and utility. For which tasks can we perform useful computations while still preserving privacy, and what exactly is the tradeoff between usefulness and privacy? We study this tradeoff for statistical query release, both offline and online, as well as for many standard combinatorial optimization tasks