Logo: University of Southern California

Events Calendar


  • CS Colloquium: Jonathan Ullman (Harvard U): Privacy and the Complexity of Simple Queries

    Tue, Feb 11, 2014 @ 04:00 PM - 05:30 PM

    Thomas Lord Department of Computer Science

    Conferences, Lectures, & Seminars


    Speaker: Jonathan Ullman, Harvard University

    Talk Title: Privacy and the Complexity of Simple Queries

    Series: CS Colloquium

    Abstract: The goal of differentially private data analysis is to design algorithms for analyzing datasets while ensuring that sensitive information about individuals is not revealed. In this talk I will present both new lower bounds and new algorithms for differentially private data analysis. On the negative side, I will present some new, nearly-optimal lower bounds on the amount of data required to release differentially private statistics on high-dimensional datasets. These results show that there is a significant "price of differential privacy" in high-dimensional datasets. We prove these lower bounds using a cryptographic primitive called a fingerprinting code that we show is closely connected to differentially private data analysis. On the positive side, I will present efficient algorithms for computing differentially private contingency tables, using techniques from computational learning theory.

    Biography: Jon Ullman is a postdoctoral fellow at the Center for Research on Computation and Society at Harvard University. He recently completed his Ph.D., also at Harvard, where he was advised by Salil Vadhan and was a Siebel Scholar. He is interested in the foundations of data privacy and its connections to other areas of theoretical computer science such as cryptography, learning theory, and game theory.

    Host: David Kempe

    Location: Henry Salvatori Computer Science Center (SAL) - 101

    Audiences: Everyone Is Invited

    Contact: Assistant to CS chair

    Add to Google CalendarDownload ICS File for OutlookDownload iCal File

Return to Calendar