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 reports@cs.cmu.edu