^November December – 2008 ^January

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.

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 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.

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.

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)