• Calendar

December 3, Wednesday
12:00 – 13:30

I will discuss a notion of privacy called *differential privacy* in conjunction with *learning problems*, and give a complexity-theoretic classification of learning problems that can be efficiently solved in a differentially private manner.

Roughly speaking, the challenge in constructing private learning algorithms is that the outcome should depend very weakly on each of the specific examples. Interestingly, it happens that two of the main models considered in computational learning theory – PAC and SQ – exactly correspond to Imposing restrictions on the way private information is distributed, and on interaction. I will discuss this correspondence, and also issues of efficiency of private learning, and a few of the open problems related to private learning.

The talk with be self-contained.

Joint work with Shiva Kasiviswanathan, Homin Lee, Sofya Raskhodnikova, and Adam Smith, FOCS 2008.