^November December – 2008 ^January

The study of ranking crosses many disciplines. Social choice theoreticians have been interested for centuries in finding a good way to rank a set of candidates. Econometricians have been asking for decades how people choose from (and more generally rank) alternative sets. More recently, information retrieval theoreticians and practitioners have been interested in ranking search query results. In verification, practitioners have been interested in ordering variable sets so as to reduce the time to detect software errors. These recent problems have been identified in both machine learning and combinatorial optimization communities. I will present my contribution on both fronts.

Randomized algorithms have been using measure concentration phenomena in countless cases, and in particular in dimension reduction and streaming. These tools have become a standard black box, and their computational aspects have been almost taken for granted. In recent work I have discovered an exciting and surprising new method for computing a standard dimension reduction algorithm (Johnson-Lindenstrauss) more efficiently than previously assumed. This method has been later used to speed up various standard high dimensional linear algebraic computations (such as SVD) and fueled increased collaboration between computer science and analysis. The main ingredient is the use of a Fast Fourier Transform and a type of uncertainty principle.

For most natural language processing tasks, unsupervised methods significantly underperform their supervised counterparts. In this talk, I will demonstrate that multilingual learning can narrow this gap. The key insight is that joint learning from several languages reduces uncertainty about the linguistic structure of individual languages. These methods exploit the deep structural connections between languages, connections that have driven many important discoveries in anthropology and historical linguistics.

I will present multilingual unsupervised models for morphological segmentation and part-of-speech tagging. Multilingual data is modeled as arising through a combination of language-independent and language-specific probabilistic processes. This approach allows the model to identify and learn from recurring cross-lingual patterns, ultimately to improve prediction accuracy in each language. I will also discuss ongoing work on unsupervised decoding of ancient Ugaritic tablets using data from related Semitic languages.

This is joint work with Benjamin Snyder, Tahira Naseem and Jacob Eisenstein.

Proteins are biological molecules which are involved in virtually every process and aspect in life - from the flexing of our muscles to our immune system response. It is widely accepted that proteins are dynamic molecules with well-defined three-dimensional structures and that understanding the structure and dynamics of proteins is crucial for understanding their function and the processes they mediate. Various computational methods exist for modeling and simulating protein structure and dynamics, but several traditional methods are limited due to the large amount of calculations involved. This talk will present a wide spectrum of methods for searching the conformational space of proteins and their application to specific cases. On the one end of the spectrum, Molecular Dynamics calculations are used for detailed analysis. On the other end, robotics-inspired search techniques are used to characterize the structure and dynamics of proteins by representing them using a mechanistic/geometric models subject to physics constraints. Two novel search methods will be discussed, aimed to characerize the structure, dynamics and flexibility of protein structures at various levels of details: the first is a hybrid method that combines an efficient robotics-inspired sampling algorithm with small scale, detailed simulations to characterize the local dynamics of proteins. The second is a fast, approximate search method that samples large scale structural changes in proteins.

Getting the deterministic complexity closer to the best known randomized complexity is an important goal in algorithms and communication protocols. In this work, we investigate the case where instead of one input, the algorithmprotocol is given multiple inputs sampled independently from an arbitrary unknown distribution. We show that in this case a strong and generic derandomization result can be obtained by a simple argument.

Our method relies on extracting randomness from ``same-source'' product distributions, which are distributions generated from multiple independent samples from the same source. The extraction process succeeds even for arbitrarily low min-entropy, and is based on the order of the values and not on the values themselves (This may be seen as a generalization of the classical method of Von-Neumann extended by Elias for extracting randomness from a biased coin).

The tools developed in the paper are generic, and can be used elsewhere. We present applications to streaming algorithms, and to implicit probe search cite{FiatNaor93}. We also refine our method to handle product distributions, where the i'th sample comes from one of several arbitrary unknown distributions. This requires creating a new set of tools, which may also be of independent interest.

Joint work with Ariel Gabizon

Alon and Tarsi have introduced an algebraic technique for proving upper bounds on the choice number of graphs; the upper bound on the choice number of $G$ obtained via their method, was later coined the emph{Alon-Tarsi number of $G$} and was denoted by $AT(G)$. In the talk I will relate this parameter to a certain weighted sum of the proper colorings of $G$. Other than the appealing notion of obtaining upper bounds on the choice number of a graph via its proper colorings (in some sense), this result has many applications. Some of them are known; for these we give unified, and often also simpler and shorter proofs; and some are new.

In the first part of the talk I will introduce chromatic, choice, and Alon-Tarsi numbers of graphs. In the second part I will state the main result and some of its applications.

We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a ``sanitization'' of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. We focus on the case where the process is non-interactive; once the sanitization has been released the original data and the curator play no further role.

Blum et al. [STOC '08] showed a remarkable result: for any collection of counting predicate queries, the exponential mechanism of McSherry and Talwar [FOCS '07] can be used to (inefficiently) generate a synthetic data set that maintains approximately correct fractional counts for all of the queries, while ensuring a strong privacy guarantee, known as differential privacy.

In this work we investigate the computational complexity of such non-interactive privacy mechanisms, mapping the boundary between feasibility and infeasibility. We show:

1. For any polynomial-size query set C and polynomial-size data universe there is an efficient algorithm for generating a privacy-preserving synthetic data-set that maintains approximate fractional counts, even when the size of the original dataset is sub-polynomial in |C|.

2. When either the query set or the data universe are super-polynomial, assuming one-way functions exist, there is no efficient general method for releasing a privacy-preserving synthetic data-set that maintains approximate fractional counts. In particular, this is a case where the exponential mechanism cannot, in general, be implemented efficiently.

3. Turning to the potentially easier problem of privately generating an arbitrary data structure (not necessarily synthetic data) from which it is possible to approximate counts for a given concept, there is a tight connection between hardness of sanitization and the existence of traitor tracing schemes, methods of content distribution in which keys are assigned to subscribers in a way that given any useful ``pirate'' decoding box, constructed by a coalition of malicious subscribers, it is possible to identify at least one of them.

Joint work with Cynthia Dwork, Moni naor, Omer Reingold and Salil Vadhan.

We will describe some recent trends in the storage industry such as, thin provisioning, de-duplication, MAID, SSD drives and others. We will show how these may be used to provide less power consuming storage while maintaining or improving price/performance.

If time permits we will also discuss power issues in the context of queueing theory.

The filesystem API of contemporary systems exposes programs to TOCTTOU (time of check to time of use) race-condition vulnerabilities, which occur between pairs of check/use system calls that involve a name of a file. Existing solutions either help programmers to detect such races (by pinpointing their location) or prevent them altogether (by altering the operating system). But the latter alternative is not prevalent, and the former is just the first step: programmers must still address TOCTTOU flaws within the limits of the existing API with which several important tasks cannot be safely accomplished in a portable straightforward manner. The recent "filesystem maze" attack further worsens the problem by allowing adversaries to deterministically win races and thus refuting the common perception that the risk is small. In the face of this threat, we develop a new algorithm that allows programmers to effectively aggregate a vulnerable pair of distinct system calls into a single operation that is executed "atomically". This is achieved by emulating one kernel functionality in user mode: the filepath resolution. The surprisingly simple resulting algorithm constitutes a portable solution to a large class of TOCTTOU vulnerabilities, without requiring modifications to the underlying operating system.

---

Joint work with Tomer Hertz (Microsoft Research), David Wagner (Berkeley), and Dilma Da Silva (IBM T.J. Watson Research Center). Based on http://www.usenix.org/events/fast08/tech/tsafrir.html USENIX File & Storage Technologies (FAST'08). Awarded best paper.

We survey lower bound techniques in communication complexity. Lower bounds in communication complexity can be roughly divided into two groups. One group uses information theoretic principles and the other uses geometric tools. We focus on the later family of lower bounds. A partial list of the geometric tools that are used is: Fourier analysis, singular values, operator norms, factorization norms and approximation theory. But perhaps the strongest tool, which in a way ties everything together, is duality. Duality and its role in proving lower bounds in communication complexity will be a main subject of our talk. Although we discuss applications to communication complexity, the techniques we present can be used in a much more general settings. We will mention connections to learning theory and circuit complexity.

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

I will discuss a notion of privacy called *differential privacy* in conjunction with *learning problems*, and give a complexity-theoretic classification of learning problems that can be efficiently solved in a differentially private manner.

Roughly speaking, the challenge in constructing private learning algorithms is that the outcome should depend very weakly on each of the specific examples. Interestingly, it happens that two of the main models considered in computational learning theory – PAC and SQ – exactly correspond to Imposing restrictions on the way private information is distributed, and on interaction. I will discuss this correspondence, and also issues of efficiency of private learning, and a few of the open problems related to private learning.

The talk with be self-contained.

Joint work with Shiva Kasiviswanathan, Homin Lee, Sofya Raskhodnikova, and Adam Smith, FOCS 2008.

The collaborative filtering approach to recommender systems predicts user preferences for products or services by learning past user-item relationships. Their significant economic implications made collaborative filtering techniques play an important role at known e-tailers such as Amazon and Netflix. This field enjoyed a surge of interest since October 2006, when the Netflix Prize competition was commenced. Netflix released a dataset containing 100 million anonymous movie ratings and challenged the research community to develop algorithms that could beat the accuracy of its recommendation system, Cinematch. In this talk I will survey the competition together with some of the principles and algorithms, which have led us to winning the Progress Prizes in the competition.

Bio: Yehuda Koren completed his PhD in CS at The Weizmann Institute on 2003. He was with AT&T Research during 2003-2008, and recently joined Yahoo! Research (Haifa)