CS&E Seminar: Amos Fiat -- 4 March 2010 - 12.00 @ Aula Magna
SPEAKER: Amos Fiat Tel-Aviv University
TITLE: Private Coresets, Data Sanitization, and Geometry
ABSTRACT A coreset of a point set P is a small weighted set of points that captures some geometric properties of P. Coresets have found use in a vast host of geometric settings. We forge a link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy. We define the notion of private coresets, which are simultaneously both coresets and differentially private, and show how they may be constructed. We first show that the existence of a small coreset with low generalized sensitivity (i.e., replacing a single point in the original point set slightly affects the quality of the coreset) implies (in an inefficient manner) the existence of a private coreset for the same queries. This greatly extends the works of Blum, Ligett, and Roth [STOC 2008] and McSherry and Talwar [FOCS 2007]. We also give an efficient algorithm to compute private coresets for k-median and k-mean queries in Red, immediately implying efficient differentially private sanitizations for such queries. Following McSherry and Talwar, this construction also gives efficient coalition proof (approximately dominant strategy) mechanisms for location problems. Appeared STOC 2009, Danny Feldman, Amos Fiat, Haim Kaplan, and Kobbi Nissim
Bio sketch -- Amos Fiat is a professor of computer science at Tel-Aviv University and holds the chair for the analysis of algorithms. He has worked in Number Theory, Cryptography, Data Structures, Online Algorithms, Privacy, and Algorithmic Game Theory, with many collaborators. He has advised some 20 graduate students, or vice-versa. He has spent a few years at Berkeley, Seattle, and (soon) Rome. He has a long collaboration with colleagues from La Sapienza going on 20 years now.
Massimo Mecella and Domenico Lembo (Chairs of the Seminars series)
Web page of the Seminars series: http://www.dis.uniroma1.it/~seminf/