Computer Science Department
School of Computer Science, Carnegie Mellon University


New Algorithms for Preserving Differential Privacy

Aaron Roth

July 2010

Ph.D. Thesis


Keywords: Differential privacy, algorithms, game theory

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.

139 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by