[Colloq] Talk, Friday, April 23 - Shiva Kasiviswanathan

[Rachel Kalweit]

The College of Computer and Information Science Colloquium presents:

Title: A Rigorous Approach to Statistical Database Privacy
 
 Speaker: Shiva Kasiviswanathan
          Los Alamos National Laboratory
 
 Where: 366 WVH
      
 When:  Friday, April 23, 10:30 AM       
 
 Abstract:
 
 Privacy is a fundamental problem in modern data analysis. We describe
 "differential privacy", a mathematically rigorous and comprehensive
 notion of privacy tailored to data analysis. Differential privacy
 requires, roughly, that any single individual’s data have little
 effect on the outcome of the analysis. Given this definition, it is
 natural to ask: what computational tasks can be performed while
 maintaining privacy? In this talk, we focus on the tasks of machine
 learning and releasing contingency tables.
 
 Learning problems form an important category of computational tasks
 that generalizes many of the computations applied to large real-life
 datasets. We examine what concept classes can be learned by an
 algorithm that preserves differential privacy. Our main result shows
 that it is possible to privately agnostically learn any concept class
 using a sample size approximately logarithmic in the cardinality of
 the hypothesis class. This is a private analogue of the classical
 Occam's razor result.
 
 Contingency tables are the method of choice of government agencies for
 releasing statistical summaries of categorical data. We provide tight
 bounds on how much distortion (noise) is necessary in these tables to
 provide privacy guarantees when the data being summarized is
 sensitive. Our investigation also leads to new results on the spectra
 of random matrices with correlated rows.

Bio:  Shiva Kasiviswanathan is a postdoctoral researcher at CCS-3 group, Los Alamos National Laboratory.  He completed his Ph.D. in the department of Computer Science and Engineering at Pennsylvania State University in 2008.

Host: Prof. Rajmohan Rajaraman