Eastern Great Lakes Theory Workshop Talk

Techniques for Private Data Analysis

Sofya Raskhodnikova, Pennsylvania State University

Saturday, September 6, 2:30 pm- 3:30pm

ABSTRACT

Consider an agency holding a large database of sensitive personal information (perhaps medical records, census answers, or web search records). The agency would like to discover and publicly release global characteristics of the data (say, to inform policy and business decisions) while protecting the privacy of individuals whose data it collected. This problem has been studied in statistics and data mining, and recently received attention in theoretical computer science.

We will define differential privacy, a notion which formalizes the privacy requirement for statistical databases. Informally, an algorithm is differentially private if its output does not depend too heavily on individual inputs. We will present several techniques for designing differentially private algorithms, and demonstrate them on computational problems ranging from finding the average and the median of individuals' salaries to general learning tasks.

Slides

Speaker Bio

Sofya Raskhodnikova completed all her university education at MIT. She received her Ph.D. in 2003 under the supervision of Michael Sipser. She was awarded a Lady Davis Fellowship at the Hebrew University of Jerusalem for 2003-2004, then spent two years as a postdoctoral fellow at the Weizmann Institute of Science and one semester visiting Institute for Pure and Applied Mathematics at UCLA. Currently, she is an assistant professor in the Computer Science and Engineering department at Penn State University.

Sofya's areas of research are randomized algorithms and computational complexity. Her main interest is the design and analysis of sublinear-time algorithms for combinatorial problems. Recently, she also has been working on privacy-preserving methods for publishing aggregate statistical data.

< Schedule < EaGL homepage