^January February – 2008 ^March

This will be a kind of an erasure coding tutorial for the layman. I will give a (very) brief survey of erasure coding, and will then concentrate on the more interesting case of rateless codes. I will present one of the first (if not THE first) works in this field, LT codes, by Michael Luby. As I am not an expert on this subject, I'll not present the finer details and proofs, but the general idea (and the more interesting points).

This will be a kind of an erasure coding tutorial for the layman. I will give a (very) brief survey of erasure coding, and will then concentrate on the more interesting case of rateless codes. I will present one of the first (if not THE first) works in this field, LT codes, by Michael Luby. As I am not an expert on this subject, I'll not present the finer details and proofs, but the general idea (and the more interesting points).

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.

We present a new method for inferring complexity properties for imperative programs with bounded loops. The properties handled are: polynomial (or linear) boundedness of computed values, as a function of the input; and similarly for the running time.

We overcome the classic undecidability obstacle by defining a ``core" programming language that is Turing-incomplete, but strong enough to model real programs of interest. For this language, our method is the first to give a certain answer; in other words, our inference is both sound and complete. This improves on previous approaches that yield sound, but always incomplete, conclusions. Further, analyzing a program takes, itself, polynomial time.

This is joint work with Neil Jones (Copenhagen) and Lars Kristiansen (Oslo).

In recent years there has been a growing interest in bridging Game Theory and Cryptography. While the standard Cryptographic settings view players as either totally honest or arbitrarily malicious, Game Theory assumes that players are rational, selfish individuals. Designing protocols for such settings poses new challenges. We investigate rational versions of two classical problems in foundations of cryptography: secret sharing and function evaluation. We show that schemes for these tasks, in which players' values come from a bounded domain, cannot satisfy some of the most desirable properties. In contrast, we suggest protocols for rational secret sharing where the shares come from an unbounded domain, but have a finite expectation.

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.

Polygonal meshes dominate the representations of 3D graphics models due to their compactness and simplicity. Recent advances in design, modeling, and acquisition technologies have simplified the generation of 3D models, which have led to the generation of large 3D models. These models consist of millions of polygons and often exceed the rendering capabilities of advanced graphics hardware. Therefore, there is a need to reduce the complexity of these models to match the hardware's rendering capability, while maintaining their visual appearance. Numerous algorithms have been developed to reduce the complexity of graphics models. These include level-of-detail rendering with multi-resolution hierarchies, occlusion culling, and image-based rendering.

View-dependent rendering approaches change the mesh structure at each frame to adapt to the appropriate level of detail. Traditional view-dependent rendering algorithms rely on the CPU to extract a level-of-detail representation. However, within the duration of a single frame, the CPU often fails to extract the frame's geometry. This limitation usually results in unacceptably low frame rates. In this presentation I will present new approaches for interactive view-dependent rendering of large polygonal datasets, which use the advanced features of modern graphics hardware, and free the CPU.

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