Moritz Hardt will present his preFPO on Thursday March 24 at 10:30 AM in Room 402. The members of his committee are; Boaz Barak (advisor); Sanjeev Arora and Rocco Servedio (Columbia), readers; Moses Charikar and Rob Schapire, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------------- Algorithmic techniques for privacy-preserving data analysis We address the problem of privacy-preserving analysis of sensitive data. Specifically we are interested in algorithms that satisfy the rigorous privacy standard called differential privacy. In the most basic setting of differential privacy we wish to respond to a number of statistical queries on a data set posed by an (untrusted) data analyst. As differential privacy forces us to give noisy answers, the basic goal is to maximize the accuracy with which we answer each query while maintaining differential privacy. Our results are the following: - We first relate this problem to certain well-studied questions in high-dimensional geometry. Assuming the truth of a deep conjecture about convex bodies, we design a new differentially private algorithm with optimal accuracy so long as the number of queries is smaller than the size of the data set and the queries are asked all at once. - We next develop a privacy-preserving multiplicative weights framework which we use to give an algorithm in the case where the number of queries may be significantly larger than the size of the data set and the queries may be asked interactively. The accuracy of our algorithm is optimal in its dependence on the database size. - We then focus on a notable special case of statistical queries called Boolean conjunctions (aka contingency tables) that are of particular importance from a statistical point of view. Neither of the aforementioned algorithms has a polynomial runtime in this setting. We give the first polynomial time algorithm for answering all Boolean conjunctions with a non-trivial accuracy guarantee while satisfying differential privacy. Our result is based on a new learning algorithm for submodular functions. This talk is based on joint works with Anupam Gupta, Aaron Roth, Guy Rothblum, Kunal Talwar and Jon Ullman.