PhD defense by Jon Ullman (Privacy Tools researcher)

Title: Privacy and the Complexity of Simple Queries
Speaker: Jonathan Ullman (student of Privacy Tools PI Salil Vadhan)
Time: Monday, May 6, 3:30 - 5:00 PM
Place: Cruft 309

As both the scope and scale of data collection increases, an increasingly large amount of sensitive personal information is being analyzed.  We study the feasibility of carrying out that socially beneficial analysis while respecting individual privacy concerns.  In particular, we consider algorithms that satisfy the strong notion of differential privacy.  Over the past decade, there has been tremendous progress in understanding when accurate data analysis is compatible with differential privacy for the subjects in the database, with both elegant algorithms and striking impossibility results.  However, if we ask further when accurate and efficient data analysis is compatible with differential privacy then our understanding lags far behind.  We make several contributions to understanding the complexity of differentially private data analysis, particularly in understanding the complexity of simple, natural data analysis tasks.