^January February – 2008 ^March

Precise control of gene activation lies at the heart of nearly all biological processes. However, despite enormous advances in understanding this process from both experimental and theoretical perspectives, we are still missing a quantitative description of the underlying transcriptional control mechanisms, and the remaining questions, such as how DNA sequence elements 'compute' expression from the inputs they receive, are still very basic. In this talk, I will present our progress towards the ultimate goal of developing integrated quantitative models for transcription regulation. I will describe a novel thermodynamic model that computes gene activation patterns as a function of DNA sequence and show that this model accurately predicts gene activation patterns in fly from DNA sequence alone.

The goal of private data analysis is to release aggregate statistics about a dataset while protecting the privacy of individuals whose information is contained in the dataset. A popular technique for privacy is output perturbation where a small amount of random noise is added to the released statistics, carefully crafted to protect individual privacy.

We introduce a new framework that expands the applicability of output perturbation. Departing from previous works, the noise magnitude in out framework is determined not only by the function $F()$ we want to release, but also by the content of the dataset itself. One of the challenges is to ensure that the noise magnitude does not become a source of information leakage by itself. For that we introduce a quantity that we call smooth sensitivity. This is a measure of the variability of $F()$ in the neighborhood of the particular instance dataset $x$. To our knowledge, this is the first formal analysis of the effect of instance-based noise in the context of data privacy.

Our framework raises many interesting algorithmic questions. Namely, to apply the framework one must compute or approximate the smooth sensitivity of $F(x)$ on particular dataset instances. We show how to do this efficiently for several functions, including the median and the cost of the minimum spanning tree.

Finally, we also give a generic procedure based on sampling that allows one to release $F(x)$ accurately on many well behaved datasets x. This procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of $F()$ is known or when $F()$ is given as a black box. We illustrate the procedure by applying k-means clustering and learning mixtures of Gaussians.

The talk with be self contained. Joint work with Sofya Raskhodnikova and Adam Smith. STOC 2007.

In many application areas, complex data sets are often represented by some metric space and metric embedding is used to provide a more structured representation of the data. In many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. In this paper we initiate the study of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structure of the space.

Joint work with Ittai Abraham and Yair Bartal