Abstract:
It is no secret that online companies, hospitals, credit-card companies and governments hold massive datasets composed of our personal and private details. Information from such datasets is often released using some privacy preserving heuristics, which have been repeatedly shown to fail. That is why in recent years the notion of differential privacy has been gaining much attention, as an approach for conducting data-analysis that adheres to a strong and mathematically rigorous notion of privacy. Indeed, many differentially private analogs of existing data-analysis techniques have already been devised. These are, however, new algorithms, that require the use of additional random noise on top of existing techniques.

In this talk we will demonstrate how existing techniques, that were invented prior to the definition of differential privacy, preserve privacy by themselves --- when parameters are properly set. The main focus of the talk will be the Johnson-Lindenstrauss Transform, which, as we show, preserves differential privacy provided the input satisfies some ``nice spread'' properties. We will show applications of this algorithm in approximating graph-cuts and in linear regression. Then, focusing on linear regression, we will discuss additional techniques that preserve privacy: regularization, addition of random datapoints and Bayesian sampling.

The talk is self-contained and no prior knowledge is assumed.