Aaron Roth

New Algorithms for Preserving Differential Privacy Degree Type: Ph.D. in Computer Science
Advisor(s): Avrim Blum
Graduated: August 2010

Abstract:

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

Thesis Committee:
Avrim Blum (Chair)
Anupam Gupta
Larry Wasserman
Cynthia Dwork (Microsoft Research SVC)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Differential privacy, algorithms, game theory